It's not that hard to move messages to folders. You can even write a rule in Mail to do it in bunches. Something like "move all mail from before <date> to <folder>" in Mail terms. Run that, say, once a month, depending on how much mail you get, and you are done. I don't know how the rules work in that old Mail system, but in the current Mail you can set a rule that if the date received is "more than" X days old Move Message to <folder>. So basically set the X for days to what you might want that would keep you well under the 3600 and you should be good to go. One small issue with Rules is that I seem to have a problem where the rules don't automatically run. I have to invoke them manually. But they do work. I did spend some time (not much) trying to figure out why the rules didn't automatically run, gave up on it and just invoke them when I want to. You could set a "to do" reminder to prompt you to clean up once a week/month/quarter/year/decade, whatever suits.
If the rules don't work, or you don't want to bother, you can sort the mail by date received, click on one, then move to the end and shift-click to select all in between, then right-click and Move them to the folder manually. Not that hard to do.