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 whole folders is exponentially faster than individual files

I may post a more detailed answer later =)