1) Consider a directory structure like
dir/playlists/main/*.m3u
             /modules/*.m3u
   /(mp3s/subplaylists)/name/{*.mp3}

in order to have a cleaner walk of
for (root, subdir, files) in dir/subplaylists/:
    glob mp3's (no if needed?, consider just iterating instead of doing a full walk as now you dont have to with this structure)
    all the other work.

2) Open the main m3u's prior to the walk, keep them open until you finish the walk (cheddar, main, Vocaloid, Idol, Touistu, Lucky lotus)
    This lessesn the load on the filesystem for opening and closing a shitload of files.
    Also removes the million try/catch to one set outside the walk.

Das it mang