I had a problem very similar with a prgram I wrote. It stored about 4 million files in the same directory. I split the files into directories using the hash of the file, with the top folder being the first 2 of the hash, and the next level being the 2nd two. So instead of 1 folder, it was 1 top level folder and 256 folders under it which each had 256 folders. 65536 folders total + the top level.
I was unable to clean the top folder, and everything (including robocopy) sucked outloud for deleting them. I wrote a quick application in .net that ran a delete command 65536 times, each time using the first 4 of the file name (which were all hashes, so they were 0-9, A-F for 0000* though FFFF* were the commands). It took maybe 30 minutes to write the program and about 5 minutes to delete the files. It was highly specialized, and it looks like you have this solved, but if you were a programmer, I would have been happy to give it out so you could modify it for your need.