Hi - I hope this isn't too big of a bump.
I just upgraded to vers 39 Opera (in Linux Mint 17 - 64 bit) and ran into the same thing. An export Bookmarks addon will export them but loses the folder hierarchy.
I did copy the bookmarks.adr file in my Home folder (the file is hidden - press control H to see them) to have that as a backup. NOTE: I have not yet tried to restore the bookmarks from that file so I don't know for sure if it works. Still, that is the way I backup my email folders (and calendar) in Thunderbird... and that DOES work.