Use Calibre. Pull all your current books into it, and import the collections information into the Kindle Collections plugin for it. (This is the a separate plugin for Calibre, discussed
here.)
Now, plug in the new Kindle, transfer the titles to it, and then use the Collections plugin to create the collections. Restart your new Kindle and it should see them.