You really need to clean up yourself - i.e., assuming your objects are already in a hierarchy, or can be put in a hierarchy, then destroy them yourself. If you're working with a collection of objects, for example, maintain a global array or something and keep a list of your objects in there. Then go through and remove them yourself before Perl does.
The problem with removing objects is when they refer to each other - obviously, the destructor needs to stop somewhere and start removing things. If you can guarantee that doesn't happen, you can write some simple code to destroy the objects before they get de-allocated. You then get to pick what order stuff happens. Presumably your objects are some kind of tree structure, and you can jsut start at the leaves and work inwards. If you have something more complicated than that, you need to think about the order in which things will get removed - perhaps you have some corner-case data structure which is causing problems (e.g. a loop)?