Ok folks some progress. Note that I've tried a million different things, each of which may have had some effect, but I'm only reporting on the final steps that I took that seem to be most likely causally related to the fix. Note also this hasn't worked perfectly: I've gone from dozens (~50?) of Unknown Title playlists to only 1 -- I'm slowly repeating the process below to see if I can also get rid of the final one. Sorry that this isn't very clear, but I tried so many things I didn't document every single one, so this is a bit of a regurgitation of as much as I can figure out after the fact. To summarise, it seems like the key is to make sure all music tracks are deleted from the iPhone, but in my case many tracks were hidden or appeared out of no where, making it difficult to delete.
Turn off Music in the Cloud if it's on, and then delete *all* the music from the iPhone. This was not as straight forward as expected, but seems like the crucial step. Despite deleting all my music via Settings - General - Storage and iCloud Usage - Manage Storage - Music - and deleting everything, tracks remained on my device. Furthermore, in iTunes, even *more* and *stranger* tracks were appearing under "Music" below "On My Device" - greyed out tracks whose "Bit Rate" was "Stream". Looking at the iPhone itself, I had only a "Purchased" playlist, and all the tracks appearing in the Music app seemed to be past purchases of the current iTunes account, with no sign of the playlist being listed in iTunes. After turning off and turning on my Watch -- in order to force it to re-index music (is this a thing?) -- the playlists included *only* the Unknown Title playlists, and not the only playlist remaining on my iPhone (the "Purchased" playlist). Deleting these purchased songs on my iPhone was not straight forward, and I tried combinations of making the entire playlist "available offline" then deleting all Music from settings, re-syncing with iTunes in the hope I could de-select the playlist (which didn't work - this playlist didn't exist on my computer, and I had not "selected" any of these songs to be synced). Unfortunately because I tried so many different things, I can't describe exactly what worked, but at one point after making all the songs available offline, I then right-clicked the iPhone in iTunes and transferred all purchases to itunes - this seemed to transfer everything, but may have also resulted in some duplicates in my iTunes. After doing this, the songs appeared as "On my device" in iTunes, and I could then highlight them all and delete them. Sometimes when I plugged my iPhone back into iTunes, more songs would appear "On my device", and so I'd have to go through the same tedious complicated processes to remove those (not knowing if one step or all steps were necessary). Also, after toggling Music in the Cloud back on and then off again, the same past purchases would re-appear. Clearly my phone thought there was meant to be music on it.
Eventually, after hours of re-deleting, re-syncing with iTunes, having the music appear again and then re-deleting, iTunes no longer showed *any* music on my device under settings, and I was not syncing any music. At this point, the Apple Watch now only showed a single Unknown Title playlist, with one track - Lana Del Rey Video Games. If I tried to play this track, the watch threw up an error. Perhaps important or unrelated, now so close to having the watch behaving as normal, the bar in iTunes showing how much space is taken up on my iPhone was still showing 2 songs at 81 meg still on my phone, but I have no idea how or where these could be.
I also signed out of iCloud and iTunes on my iPhone at some points, but I'm not sure if this had an effect - again I'm sorry that I didn't document the order of the steps more carefully - truth be told I wasn't expecting any of this to make a difference.
After repeating all this just now, I don't seem to be able to get rid of Lana and the final playlist from my iPhone... now there's nothing that I can delete, because iTunes and iPhone are both showing no songs whatsoever, even after toggling iTunes on/off and Music in the Cloud on/off. If I sync Lana properly from iTunes, I simply get two appearances of it on my Watch.
Also note that this processes of constantly checking the watch (and restarting it constantly, perhaps unnecessarily), chewed up a lot of the watch's battery power, so only do this if you're close to full charge or have the charger handy.
I'll answer as many questions as I can if this is not clear (it's not), but I don't know how much more my ramblings will help specific instances. Please report back if any of this does or doesn't help.
Best of luck.