For example something that can tell me how many scalars, and estimate their data size + Perl overheads on a per-package basis in bytes?

You could put Elian's Devel::Size to good use. Something like this might be of help

use strict;
use Devel::Size qw(size total_size);

sub mem_size {
  my($pkg, $type) = @_;

  die("mem_size(): unknown variable type '$type'\n")
    if $type !~ /^(?: HASH | ARRAY | SCALAR )\z/x;

  my $ret = 0;
  no strict 'refs';
  for(values %{"${pkg}::"}) {
    $ret += ( $type eq 'SCALAR' ?
                size( ${ *$_{$type} } ) :
                total_size( *$_{$type} ) )
      if defined *$_{$type};
  }
  return $ret;
}

print "SCALAR mem usage in main:: is ",
      mem_size("main", "SCALAR"), $/;

__output__

SCALAR mem usage in main:: is 2098
[download]

Or even better something that can take a nested data structure and summarise how much data + overhead (hash buckets, key arrays?) is being used at a specified depth?

Again you could use Devel::Size for this task by employing total_size() at the desired depth. Also a hash in scalar context will return the number of used buckets and the number of allocated buckets (see. perldata).

Or code analysis tools that let me know about long lived large data structures that are not referenced again?

Data structures that are no longer referenced will be garbage-collected so you needn't worry about that.

Does releasing a hash make the recovered memory available to subsequent Perl structures?

That it does. Once a variable has been 'released' it's memory is then available to future variables so perl won't just keep on growing.
HTH

_________
broquaint