Dealing with roaming profiles, I've seen this quite a bit. In my experience, sending any sort of delete command is not as fast as using Robocopy to /MIR an empty folder to the destination. I don't have any raw data or actual metrics that this is faster than any of the already mentioned options, but it is considerably faster than using the Explorer shell.
Just make a new empty directory, or reference a current empty directory, then run the following command:
robocopy x:\path\to\emptyfolder x:\path\to\delete /MIR /R:1 /W:1 /MT:128 /LOG:x:\path\to\logfile.log
/MIR :: MIRror a directory tree (equivalent to /E plus /PURGE).
/R:1 :: number of Retries on failed copies: default 1 million.
/W:1 :: Wait time between retries: default is 30 seconds.
/MT:128 :: Do multi-threaded copies with n threads (default 8).
n must be at least 1 and not greater than 128.
This option is incompatible with the /IPG and /EFSRAW options.
Redirect output using /LOG option for better performance.
You'll want to LOG when using MT, there is definitely a measurable delay when displaying the output on screen.
By using /MT:128 as an option, it will max out the amount of files it can 'delete' at one time.
Also note that if this is your first time with Robocopy, you should do a dry run with the /L flag:
/L :: List only - don't copy, timestamp or delete any files.
Then check the logs and ensure the actions match what you want.