Like the others said use File::Find::finddepth to recursively toast directories (obviously be very careful with this as it acts exactly like rm -r). If you have the perl cookbook there is an explination on page 325 of this exact thing.
If you don't have that then take a look at the code in the File:Find module (win32: %perl_install_dir%\lib\File\Find.pm ).
Also remember that the 'rmdir' command won't delete directories if they have files and/or subdirectories still in them.
Thanks,
djw