It would be way nicer if it was in the same XML file as the other export stuff, and even more so if the user could indicate an image to use, and indicate what genres he wanted them to show up in.
But in the short term, just getting them into the export XML would be a good start.
It doesn't seem like a file being in a playlist would be a problem. If, during the export, you assign an incrementing count to each track as you spit it out (not the playlists but while outputing the other content.) Then the playlists would have to be made up of those files (right?), so the playlist could be just a list of space separated indices into the linear list of tracks. It wouldn't matter if the same number was in a playlist more than once, would it? If the playlist is nothing but a collection of pointers to other (non-playlist) tracks, it seems you could have a playlist that was just the same song over and over and it wouldn't matter much.
If they can apply attributes to songs in the playlist that are stored as part of the playlist data, then I could see the problem since you could have the same file in a playlist multiple times or in multiple playlists and set different info on them.