mp32m3u is a tiny C program that can generate m3u playlists (with readable titles) from a passed in list of mp3 files. It reads the id3v1 tag of the mp3 and uses it to create a human readable line for the m3u. It will also prefix file links with an HTTP URL. The code is very straightforward and any URL prefix editable in a macro at the top.
I have a single master script that generates playlists for each letter of the alphabet, new music, the complete set, etc.
Originally, I used a Python script to do this, but it was slow, taking around 10 minutes due to the overhead of starting the interpreter to parse the ID3 tag of each file. Using this simple C program with it's own (5 line and very efficient) ID3 tag parser cuts that down to about 10 seconds for around 5,000 songs (and that metric is from my NSLU2/slug, where the files are served from).
For example, to generate an m3u list for every song in your collection starting with the letter S:
mp32m3u `find . -name 'S*.mp3'` > playlist.m3u
I use a simple Artist/Album directory structure which makes it easy to include songs by a certain artist using this trick.
I also have a CGI web interface that can construct m3u files in a user-friendly way. It has so far not quite gotten through the wife acceptance test and I'll get round to uploading it when it passes.