Memory allocation is a fairly complicated subject, and I'm not sure what Devel::Size does exactly. Moreover, I am really not a specialist on these things, so what I will say next is not at all from any insider knowledge on how Perl (and the underlying C functions) allocate memory, but from what I have read from people knowing these things presumably much better than I do. So, take it with a pinch of salt, I may be misunderstanding some of these things.

In general, I would not expect the overall memory footprint to decrease when you delete some data structures. Even if some memory has been freed, it will probably not show in these stats (due, among other things, to memory fragmentation). But if you have freed some of it by deleting some hash entries, then there is good chance that your program will be able to reuse the freed memory, so that creating a new hash entry will not increase the overall memory usage.

Update: Fixed wrong link for the Devel::Size module.