For anybody else from the future, Emil's code worked for my similar application with one minor edit. I was having issues with the naming convention returning only the last fc name in the dictionary, so changed os.path.basename(fcFullPath) to just filename:

import arcpy
import os

workspace = "D:\xyz"
outdir = "D:\xyz\merged_dissolves.gdb"

walk = arcpy.da.Walk(workspace, datatype="FeatureClass", type="Polygon")
di = {}

for dirpath, dirnames, filenames in walk:
          for filename in filenames:
             fcFullPath = os.path.join(dirpath, filename)
            #  print filename
            #  print fcFullPath
             #try adding feature class to dictionary with already-existing key
             try: di [filename] += [fcFullPath]
             #key not in dictionary yet. Create key
             except: di [filename] = [fcFullPath]



#iterate dictionary
for filename in di:
    #get merge feature classes and print output filename from dict
    mergeFcs = di [filename]
    print(filename)
    output = os.path.join(outdir, filename + "_merge")
    arcpy.Merge_management(mergeFcs, output)

For anybody else from the future, Emil's code worked for my similar application with one minor edit. I was having issues with the naming convention returning only the last fc name in the dictionary, so changed os.path.basename(fcFullPath) to just filename:

import arcpy
import os

workspace = "D:\xyz"
outdir = "D:\xyz\merged_dissolves.gdb"

walk = arcpy.da.Walk(workspace, datatype="FeatureClass", type="Polygon")
di = {}

for dirpath, dirnames, filenames in walk:
          for filename in filenames:
             fcFullPath = os.path.join(dirpath, filename)
             #try adding feature class to dictionary with already-existing key
             try: di [filename] += [fcFullPath]
             #key not in dictionary yet. Create key
             except: di [filename] = [fcFullPath]



#iterate dictionary
for filename in di:
    #get merge feature classes and print output filename from dict
    mergeFcs = di [filename]
    print(filename)
    output = os.path.join(outdir, filename + "_merge")
    arcpy.Merge_management(mergeFcs, output)