OK, this worked for me!!!!
My bookmarks are under "Bookmarks Menu" but I followed your instructions doing the exact same thing you did. I right clicked and sorted by Name, followed by a Command Z to revert to my original order. I then moved the recent bookmarks that were jammed at the top of the list to their proper spots I wanted them. Went to check on my iPhone and those bookmarks stuck at the top now in fact moved to the spot I put them on my Mac.
I then did a test to see if this is really fixed - tried to save some new bookmarks and they are now saving at the BOTTOM of the list as it did before AND seem to carry over across devices as well! Even when I move the new bookmark, it carries over to the new spot across devices.
Will continue to test but looks like this is the fix!