Sounds like a job for File::Find. How about something like this?

#!/usr/bin/perl -w
use File::Find;

finddepth(\&output, '.');

sub output {
    return if $File::Find::name !~ /.mp3$/;
    print "<p>$File::Find::dir</p>\n";
    (my $n = $File::Find::name) =~ s/.*\///;
    print "\t<blockquote>$n</blockquote>\n";
}
[download]

Update:
I'm not sure what you mean by it's printing out a directory at the top of MP3 name. If you'd like the directory name to print only once then you can save the previous one in a global maybe and then check to see if they match. If they don't match then print the name of the directory. ie.

#!/usr/bin/perl -w
use File::Find;
use vars qw($prev);
finddepth(\&output, '.');

sub output {
    return if $File::Find::name !~ /.mp3$/;
    print "<p>$File::Find::dir</p>\n" if $File::Find::dir ne $prev;
    $prev = $File::Find::dir;
    (my $n = $File::Find::name) =~ s/.*\///;
    print "\t<blockquote>$n</blockquote>\n";
}
[download]

By the way, it's much easier to use finddepth for your recursive search, than to roll your own recursive search.
HTH