Quick suggestion:
- Iterate through all the records in the database
- Group them by folder
- See if there are other items in the folders
- Moving folders is exponentially faster than individual files
- If the files are on different drives, or you are not allowed to change the directory structure, you are pretty much SOL and will just have to be patient =)
I may post a more detailed answer later...