Hi, I think I've found at least a partial solution to this problem.
I had the same problem of not being able to delete a folder. I tried to delete it on different devices, but it always eventually game back to all devices. Finally I decided to launch Notes on all of my devices simultaneously and then deleted the rogue folder on every device. Note that I also had iCloud open on a Mac and I deleted the folder in question from there, too.
At this point I noticed that the folder popped back quite soon on one of the devices, my MacBook. So, the MacBook seemed to be the one with a corrupted folder, refusing to be deleted and eventually propagating back to all the other devices, too.
To test my theory, I disabled Notes in the iCloud preferences on my MacBook. This caused all Notes application content – notes and folders – to vanish from the Mac. After a while I re-enabled Notes in the iCloud preferences and let Notes download everything from iCloud again, and voilà , the problematic folder was gone for good! Hope this helps some of you.