I've experienced something similar with Empty Outputs Generated from tools like dissolve, union, merge when the shapes have too many features.
What constitutes too many features could be anything from the shapefile technical standards, software or harware limitations, to the good old glitch/bug.
When I experience these errors, I will set up the operation in model builder (add your inputs, tools, set up parameters, validate entire model) and export to python script which I run outside of ArcGIS in a cmd prompt, or the python command line. I can compare results, and even productivity.
And like you've already tried, do this same process when using different output and input types: ie, shapefile vs feature class (gdb feature).