I'm not sure if this is specific to the Music app for Windows 8.1 or not, but on the left side of the Music app I have a "New Playlist" option, as well as the ability to import playlists.
View attachment 40060
Ya I'm not sure either. Thought it might be in AppData but no dice, though I did notice that the playlists synced to the Music app on my Lumia 920.