Here's how I might do it:

use strict;
use warnings;
use Date::Manip;

my %files;
while ( my $line = <DATA> ) {
    chomp $line;
    my( $key, $value ) = split /\s*=>\s*/, $line;
    $files{ $key } = $value;
}

my @sorted_keys = 
    map { $_->[0] }
        sort { Date_Cmp( $a->[1], $b->[1] ) }
            map { [ $_, ParseDate( ( split /\|/, $files{$_} )[0] ) ] }
                keys %files; 

print "$_ => $files{$_}\n" foreach @sorted_keys;

__DATA__
index.html => Mon Oct 11 00:08:11 2004|12963
screenshot.jpg => Sun Oct 10 13:18:30 2004|234997
legal.html => Mon Oct 11 12:57:03 2004|13448
stylesheet.css => Mon Oct 11 13:57:28 2004|697
about.html => Mon Oct 11 00:08:08 2004|13225
archive.html => Mon Oct 11 00:08:09 2004|12872
postinfo.html => Fri Oct 1 23:49:15 2004|2457
contact.shtml => Mon Oct 11 00:09:48 2004|11366
services.html => Mon Oct 11 00:08:17 2004|14256
metatags.pl => Mon Oct 11 14:05:44 2004|28668
tools.html => Mon Oct 11 15:35:47 2004|14632
robots.txt => Sat Oct 9 03:35:15 2004|73
_vti_inf.html => Fri Oct 1 23:49:15 2004|1754
report.shtml => Mon Oct 11 00:07:03 2004|11686
[download]

If the dataset is small, you may not care to bother with the Schwartzian Transform that my solution uses... its performance gain might not be worth the extra effort. For larger datasets, it can prove beneficial though. If you've already split the date / size info into anonymous arrays held in the hash, there'll be no need for the transform at all, except perhaps to parse the date with ParseDate()

I chose to use Date::Manip to transform your dates into something that can be easily compared (and sorted). I also used that module's Date_Cmp() function to perform the comparison within the sort routine. I could have used the cmp operator instead, but the Date_Cmp() function is also timezone friendly.