It seems that you are running the external program mv for every rename. I'm not sure if that's the performance hog in your case, but I think it would be better if you used perl's builting rename function instead, or, if you're moving to a different filesystem, the move function of the File::Copy module which is in the core of current perls.

Update: to try out easily if that's the problem, it may work to comment out the backticks line and see how fast the script runs that way. Of course, it won't move the files then.