As you mentioned, File::Find to search for files, File::Spec to handle dealing with paths (or possibly File::Basename to separate the path and file name), and File::Copy to move the files. (I thought about suggesting Parallel::ForkManager and spawning off multiple children to do the copying, but realized you would likely not see a performance improvement as a result.)
Regarding collisions, I would suggest scanning for files in a pass, then do all of the file moves in a second loop.
Hope that helps.