The idea behind this script both terrifies, and excites me.

The script itself however frightens me, because there are some edge cases that can have some relaly nasty behavior...

• There's a risk of some silent catastrophic user error if a person inadvertently attempts to rename two different files to the same file (ie: "a->x and b->x" ... or if they mean to do "a->b and b->a" but they forget to change one and wind up with a->b and b->b). It would be pretty easy to prevent this type of error by doing an "exists" around line #60
• There's a really bad assumption in your "handle overwriting name changes" ... it will work for a->b and b->a but not any other generalized overlaps like "a->b and b->c". This is because the loop over the keys only checks for the existence of the "target" file as a key in the hash and if it exists it creates a temp file -- but it never looks at the value that "target" had in the hash when moving the tmpfile, it just assumes you wanted a straight swap.
• Even if you fix the previous bug by using mv($tmpfile, $files{$files{$fname}}); instead of mv($tmpfile, $fname); I still think it's possible you're going to wind up edge cases where things fail depending on what files get processed in -- in particular consider the case of "a->b and b->c and c->a"

I think the only safe way to deal with all of this is that if you detect your $target is already a key in the hash, you need to mv($target,$tmpfile) and then update the hash, ala: $files{$tmpfile} = $files{$target}; delete $files{$target};. It complicates things because you can't do a simple loop over a one time copy of the keys, but that's not a big deal. Just do a "while (keys %files) { $fname = (keys %files)[0]; ...; delete $files{$fname}; }" type flow instead.