I would separate a couple of part here:
- Long-term product development strategy
- Everyday release management
First, you need to know where you're going so you need to figure out goals which your product should achieve and ways (big chunks of functionality) to achieve that goal. That gives some kind of high-level roadmap which you plan to follow. As it takes into account business strategy you should have there big milestones, like delivering quarterly big hairy version with a big bunch of new thrilling stuff to your customers. And this is the point where you start dealing with releasing product.
You need to know which versions covers which features and when they go into production. Then, you probably need to prepare reasonable amount of documentation if you have once-in-quarter-or-less-frequent-release strategy.
Second, you mention agile as your method of choice and 3-week long timebox. It means that you should have something to release once every three weeks. And for such releases I'd try to limit amount needed documentation to as little as possible. If you don't push each of such versions into production that's good because you can perfectly skip most of documentation, especially parts regarding planning each sprint as a separate product. If you do push each version into production it's even better -- I believe there's little documentation which is really crucial if you release in such frequent manner. You should also have pretty repeatable process after a few consecutive releases so it definitely shouldn't be as painful as you say.
If you want to make it even better think about even more frequent releases. I don't how it is now, but some time ago guys building StackOverflow were trying to push something new into production on daily basis. Then incremental value you deliver is small but your increments are very, very frequent. This basically mean you just have to limit amount of different formalities around release process to lowest possible level which gives you powerful motivation to find lowest reasonable subset of documentations and planning you really need.
Note: that the everyday release strategy is just a way of fulfilling long term strategy so it should be means to achieve some bigger goals. As long as you are aligned with your high-level plan it usually doesn't really matter whether your nth release goes live on Tuesday or on Wednesday.
