If I understand, you can simply narrow your regex to match up to the first underscore, and see if that 'exists':

foreach my $files(@files) {
  $c++;  

  if($files=~m|.*/([^_]+)|) {
    $f_name = $1;
  }

  if (exists $filelist{$f_name}) {
   print "$c - Found and to be deleted: $files\n";
  }


}
[download]

I might go as far as:

for (@files) {
  $c++;  

  if(m|.*/([^_]+)| && exists $filelist{$1} ) {
     print "$c - Found and to be deleted: $_\n";
  }
}
[download]