It's really simple. Each queue is a separate leveldb database on disk. Messages are stored as key/value using incremental ids. Head and tail of the queue are kept in memory and get initialized on startup via db scan.
But deletes are going to have a big impact still, and (working from my failing memory of LevelDB internals) I think might actually be the pathologically sad case.
Stick about 10GB of small entries in it (should be enough to create all the levels) and then see what happens.
Also, you could reserve the persisted [H|T] for controlled shutdown scenarios. Basically anything that isn't complete system failure if you're properly trapping signals.