mm @Cat good suggestion indeed, you have my vote. I haven't been able to use bookmarks a lot yet due to the lack of a single-column menu, but still..
I can see three possible places for to create a new folder if any/all of these are exactly what you would had liked?
- the 'add this page to' has a fourth button in the blank middle labelled 'create new folder' which would basically cause a second pop-down just below the first one
- for users that only wanted to move existing bookmarks into new folders I suggest that in the sidebar, there is a small shiny folder icon to the right of the sidebar menu button itself (the downward symbol)
- and in regarding to #2, for users who users the edit bookmark menu instead hmm I'm not so ux-certain but I could proposal that the blank space between 'bookmarks xx items' text and search box has a simple 'new folder' textual button