Your problem is that you're thinking you need a HoH and you create a HoH, but what you want is a HoHoHo... of indefinite depth. That means you have to loop through the levels of the hash. pg showed you a way of doing that. Here are three more.

Easier to read/understand alternative:

foreach my $file (@filenames) {
   my $h = \%files;
   my @parts = split(/[-_.]/,$file);
   my $last = pop(@parts);

   foreach (@parts) {
      $h->{$_} ||= {};
      $h = $h->{$_};
   }

   $h->{$last} = 1;
}
[download]

Shorter alternative:

foreach my $file (@filenames) {
   my $p = \\%files;
   my @parts = split(/[-_.]/,$file);
   $p = \(${$p}->{$_}) foreach @parts;
   ${$p} = 1;
}
[download]

Even shorter, but it's the same algorithm:

foreach (@filenames) {
   my $p = \\%files;
   $p = \(${$p}->{$_}) foreach split /[-_.]/;
   ${$p} = 1;
}
[download]

Question:

Have you considered the case where you have the files "example.txt" and "example.txt.bak"? Currently,
If you get the longer one first, the longer one will be erased.
If you get the shorter one first, the program will die.