I would try to avoid self written loops and use Perl builtins like map grep for it if has to be efficient:

(untested)

#my @files2del = map { ($hash{$_}->{Size} > $sizelimit ? $_ : () } key
+s %hash;
my @files2del = grep { $hash{$_}->{Size} > $sizelimit } keys %hash;
delete @hash{@files2del};  # deletes paths from hash
unlink @files2del;         # deletes files from disc
[download]

Also:
Like moritz already pointed out: cmp isn't what you want but <=>.
Keep your hash key names all lowercase as long you don't have a good reason to do otherwise.

Update: Like salsa wrote (while I wrote my post): the use of grep instead of map is better in this case. See perlfunc for both.
Update 2: Thanks moritz, I always appreciate all feedback. In this case you were just replying faster than I was updating. :-)