Devel::Size should work on tied anything -- there's code in it to detect attached magic structures and extract their sizes. I thought I had the code in there such that it wouldn't trigger the magic when walking the internal data structures, but I may have bobbled that. Devel::Size, unfortunately, doesn't have a particularly comprehensive test suite. (In part because the size of things is so terribly dependent on architecture and in part because I couldn't figure out a good way to test it)

I'll grab this code and start beating on Devel::Size (which needs some beating anyway, as there's a bug in 0.64 that needs fixing) and see what I can see.