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.