A couple of tips:

• Paths often have numbers, so they're a prime candidate for natural sorting. The same distro provides the means to do this.
• tr/// is faster than s///.

use Sort::Key::Natural qw( natkeysort );

my @sorted =
   natkeysort { tr|\\/|\0|r }
      @paths;
[download]

Of course, this still ignores case-insensitive volumes, as well as paths containing «.» and «..». But what can you do? (Well, «.» can be addressed, but there's no obvious solution if any exist for the rest.)

I would agree if this produced output like keysort but with better number handling, but because the null characters are treated equivalently to any other non-word characters, and natsort splits the words on these, the output differs more than just on numbers. Note that 'abc-def' now sorts before '/abc/def' in the output:

Ordered with keysort:
    /abc
    /abc/1/2/a/b/c
    /abc/2
    /abc/22
    /abc/3
    /abc/def/1/2/a/b/c
    /abc!def/1/2/a/b/c
    /abc-def/1/2/a/b
    /abcdef/1/2/a/b/c
    /usr/a
Ordered with natkeysort:
    /abc
    /abc/1/2/a/b/c
    /abc/2
    /abc/3
    /abc/22
    /abc-def/1/2/a/b
    /abc/def/1/2/a/b/c
    /abc!def/1/2/a/b/c
    /abcdef/1/2/a/b/c
    /usr/a
[download]

Sort::Key::Natural provides a low level function mkkey_natural for that:

# untested
use Sort::Key qw(keysort);
use Sort::Key::Natural qw(mkkey_natural);

@sorted = keysort { join "\x00\x00", map mkkey_natural, split /\//, $_
+ } @paths;
[download]

The double 0 char (\x00\x00) is used for joining because mkkey_natural uses a similar trick in the generated keys.

Of course, this still ignores case-insensitive volumes, as well as paths containing «.» and «..». But what can you do? (Well, «.» can be addressed, but there's no obvious solution if any exist for the rest.)

There's also portability issues like what File::Spec handles. Volumes and different path separators, etc. You can also be processing a list of paths generated on a different system (e.g. processing windows paths on unix).