A few thoughts ...
For the absolute, no holds barred in final output quality, rendering right to the required resolution is definitely best.
But, digital files have an amazing ability to be uprezzed to high quality large format prints. I've printed a 4MP ISO 800 digital still on outdoor vinyl at 5x7' feet and had people amazed that they could possibly come from a camera of that resolution. They were viewing the image from about 10 feet away.
Now I'm printing 10MP ISO 3200 and 6400 images in house at roughly 4x6 feet and they look better still - printed on an HP z3100 on some nice semi gloss paper stock.
The fact of the matter is that your viewing distance is a major factor in determining what resolution you will need in your final output.
If you are talking nose-to-the-print inspection of every detail then you will need the highest resolution possible. In photography, that's either really large format negatives and scanning or possibly photo mosaic of multiple digital shots to get extreme resolution. If you are talking looking at these images from a distance at which you will be able to take in the entire image at one time, then the required resolution drops dramatically (for example, billboards are generally a very low print resolution, but they can look really good when you are driving by on the highway, 50 or 100' away).
I've yet to see any digitally generated content that could live up to that sort of in your face resolution and scrutiny on a large scale - the level of detail needed in the image is incredible and usually falls apart on digitally generated content - mostly because of the time needed to create the detail by the artist.
You really won't need 9000x6000 sized files to produce some stunning output. That's 54MP ... Those 4000x3000 renders you did are approximately 12MP and - if the files are treated nicely - could produce some really great output up to some very large sizes.
One of the great things about Terragen (or any fully digitally generated output) is that you don't have to worry about digital signal noise, lens defects like chromatic abberation, lens flare, diffraction, etc., etc. like you have to in real photography. The output is extremely clean and can be upsampled beautifully.
So, don't think you HAVE to be able to render 9000x6000 to print those prints. And you don't have to have special software for the uprezzing. Bicubic interpolation works great on most images. That's available in most image editing packages out there.
Regards,
Micheal