What it sounds like what you really want is different tests with varying level of details but only run one big test script. The thing about tests is that it cost nothing to keep making them, if you make one big test script you might spend as much time just trying to debug your test script as you would your module.

Why not start with a strategy of making a number of different tests with each one in its own file; each test has different layers of complexity. Start with small simple tests as your core and write them. As you need add complexity to your tests, focus a test on one aspect of your module. Your tests are easier to maintain because they are limited in scope. Another reason to limit the scope is that it easier for you to focus on that one piece. I cannot imagine, with the things that you are working with, trying to test everything at once. For example these could be a list of test files,

basic.t       # Basic functionality (Does a single level hash or array work?)
embedded.t    # Embedded functionality (Does a HoH, HoA, AoH, AoA, and deeper work?)
wide_data.t   # What about wide hashes and arrays (4000+ keys)?
deep_data.t   # What about deep hashes and arrays (4000+ levels)? Does every level behave appropriately? 
filter.t      # What happens if we use filters on the keys? The values?
internals.t   # What about changing some of the internal key values?
change_wide.t # Changing the hashing function make a difference?
change_deep.t #
clone.t       # Does cloning work?
import.t      # What about importing and exporting from standard Perl data structures? tied datastructures?
export.t      #
locking.t     # How about if I turn locking on and off?
dbm_deept.t   # What about creating the db using tie vs. DBM::Deep->new?
concurrent.t  # How about concurrent access?
auto_bless.t  # What about turning autobless on and off? What about locking? autoflush? 

This way might be more redundant, however, by building it in layers you will be able to more easily identify when you broke your code because the simple stuff will start breaking right away and you can focus your immediate efforts on fixing that before you attempt to address your very specific and detailed tests.