Bryan is correct.
Deleting a Playlist only deletes the small, numerical references to the actual songs placed on the iPod. The actual space used (byte-wise) by a playlist is quite small.
If you have no room to create any more playlists, then you will need to remove one song on the iPod (pick a small one). That should free up enough space to create many new playlists.