my %file_times;

# Then in the wanted function:
$file_times{$File::Find::name} = -M $_;
[download]

If you want to avoid modifying existing code too much, you could try something like

use File::Find;

my @files;

find(\&collect, ".");

sub collect { # 'wanted' function replacement
    push @files, [ 
                  $File::Find::name,
                  (stat)[9]  # mtime
                 ];
}

sub wanted {  # your original 'wanted' function
    # ...
}

my @files_by_age = sort { $a->[1] <=> $b->[1] } @files;

for my $entry (@files_by_age) {
    my $fullname = $entry->[0];
    my ($dir, $name) = $fullname =~ /(.*?)([^\/]*)$/;

    # set variables that File::Find would have set
    $File::Find::name = $fullname;
    $File::Find::dir  = $dir;
    $_                = $name;
    
    # depending on whether you need it, you might want to
    # chdir() into the directory
    # ("left as an exercise ..." :)
    
    # call wanted() function as File::Find would have done
    wanted();
}
[download]

(Depending on exactly how you're using File::Find, you might need to finetune the approach... this is just an outline of basic usage.)

almut:
I found a very neat way of doing it without modifying any of the existing code, yes I had to change the way I was calling the find.
Here I go..

find( 
 {wanted=> \&wanted, 
  preprocess => \&preprocess }, #Added this line thats it
 '.');

#Added this function as well
sub preprocess
{
my %afiletimes;
foreach(@_)
{
  $afiletimes{$_} = -M $_ if -f ;
}
@_ = sort { $afiletimes{$b} <=> $afiletimes{$a} } keys %afiletimes;
}
[download]