Problem deleting files

I needed to delete about 2.7 GB of 500,000 files yesterday and it
seemed that it was taking far too long. I was deleting these files
using the command prompt. I opened another command prompt to measure
the progress by seeing how much free space became available every
minute. It was only about 2 MB, thus the system was only deleting
about 370 files per minute. At this rate it would take more than 22
hours to complete. I ended up reformatting the drive because this
would take only 25 minutes.

Does anyone have any idea whether or not deleting 500,000 files of an
average of 5 KB each should take more than 22 hours on a fast quad-
core sata drive machine? What could have been going on?