As long as your objects are not referring to each other or creating circular references in other ways, they should be removed when they go out of scope (technically, when their reference count goes to 0).

If you want notices of your objects being destroyed, you can create a DESTROY method in their class:

package MyClass;
sub DESTROY {
   my $self = shift;
   # assuming object has a "name" property
   warn "object $self->{name} is being destroyed now";
}
[download]

Depending on your problem, creation and destruction of your objects might be a bottleneck (I've hardly ever been in that situation, but still). If so, you could consider "reusing" the same object, or using class methods (if you're only using one instantiation at a time anyway), or getting rid of the object altogether and using hash references or scalars, or array refs instead.

Give Devel::DProf a shot, before you start optimizing. It will probably give you more insight in what part of your code is causing the problem.