how could "modifying the input list" have any side-effects here?

You'd be surprised in some instances.

$ perl -le'
   for (1..2) {
      print map { my $x=$_; $_="!"; $x } 1..5
   }
'
12345
!!!!!
[download]

But that's not the case here.

I can see no bad practice in rewriting a hash and a sorted list of its keys in one pass:

%hash = map { my $v = $hash{$_}; s/ /_/g; $_, $v } @sorted;
[download]

That was actually hard to understand, but I suppose a comment would solve that.

Keep in mind that perlcritic will err on the side of false positive over false negative. Otherwise, it would be redundant with -w. Even if the rule is sound doesn't mean there aren't exceptions.