How to clean up orphaned files from uploads folder

I have a client who never sorted her uploads into month & year folders, so now there are over 13,000 images in her uploads folder. Many are orphaned files (some are from regenerating thumbnails at different sizes, some are from a gallery that no longer exists, etc). I would like to delete some of these files.

I tried the upload janitor plugin but it times out because there are so many in the directory.

Can anyone recommend a way to do this? Thanks!