[Milhouse]

My "stats" from today's cleanup: ~20 minutes for ~4900 files summing up ~80MB. 
20 minutes is a lot of time for deleting only 80MB, but 20 minutes is also a lot for 4900 files... Deleting the thumbnails folder altogether would take only a second or two.

I'm pretty sure the P (prune) command is just correlating the contents of your media library with your texture cache library, and then removing anything from the latter that is not referenced by the former. The time taken to perform this task depends on the size of the respective libraries, the speed of the device being cleaned (and, if being performed remotely, the speed of the network between the machine running the script and the device being cleaned). So if you have a very large library and are cleaning a slow machine (eg. RPi1) then yes, it could take a while just to remove only a few files as it has to compare the entirety of both libraries to determine there are only a few files that can be removed.

I don't know how large your libraries are, or what device you are cleaning, but it is entirely possible that it could take several minutes - it has to crunch quite a lot of data!

I just noticed that I forgot to use vclean first

The only reason I mentioned vclean is because cleaning the library can often incur significant delays while Kodi communicates with potentially non-existent remote web services - if you're not cleaning your library then this isn't the cause of the delays, I'm not suggesting you run vclean!