Hi jruk, this part is normal:

New bookmarks and folders are always added at bottom of list...

But this part sounds like a bug:

... and Sort will not move them.

Where are you right-clicking? Usually you need to use either the Library Dialog ("Show All Bookmarks" / Ctrl+Shift+b) or the Bookmarks Sidebar so you can right-click on "Bookmarks Menu" to get Sort by Name to even show up -- it only works on the right-clicked item, whether it's the top level of the menu or a folder.

One other thought: if the new bookmarks/folder are below a separator, Sort by Name will sort them within that separate group only and not move them into the first group. You should be able to remove an unwanted separator in the Library dialog (right-click the separator > Delete).

Using Library I can sort Bookmarks. I have a lot of folders in Bookmarks menu. What threw me was I was right clicking on a folder in the bookmarke menu and selecting Sort and expecting all the entries in the displayed menu to be sorted (instead it was sorting the entries within the right clicked folder - which were already sorted so looked like no action). Pity there is no built in option to have entries automatically maintained in a selected sequence although ther appear to be several addons addressing this.