Quick suggestion:

 1. Iterate through all the records in the database
 2. Group them by folder
 3. See if there are other items in the folders
 4. Moving folders is exponentially faster than individual files
 5. 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...