If you use print $song, it prints the filenames, but not the full paths, right? Since the file is not in the current working directory, you need to use the path with the filename so that Perl knows where to find the file.

my $dir = 'd:\my files';
opendir(FILES, $dir) or die "Can't opendir '$dir': $!\n";

# read in the playlist and the files, create the hash, and so on...

foreach $song(@filelist) {
    if(!exists $playlist{$song}) {

         unlink("$dir/$song")
             or warn "Can't unlink '$dir/$song': $!\n";

    }
}
[download]