Are you sure $element is a key in %$HoHref ? What you're doing does work:

$ perl -e'my $hohr = {foo=>{},bar=>{},baz=>{}};print delete ($hohr->{b
+az}), $/;print keys %$hohr'
HASH(0x804b5c0)
barfoo$
[download]

Perhaps you have unchomped newlines in your keys or $element? That could explain why your keys aren't found.