I might use sed for that: Generate the "mv" commands, and then execute them.
(Actually, most often, I use vim.)