I assume you have textured you 1 million polygon model?
You can bake the texture into the vertexmap in Zbrush.
I don't how the vertexmap will go thru decimate, so you need to experiment with that.
I think you can save as color-stl, and upload that to shapeways.
If you have a separate texturemap, and want to use it instead of the vertexmap ( which has less then perfect results)
Then you need it to save it as vrml 2.0
You need to edit the vrml file and remove 'file:///' before your uvmap-name. For example: beast.jpg is referenced as
file:///beast.jpg
change it to:
beast.jpg
You will need to have the uvmap and your vrml-model in one zip-file.
Textured objects are a pain in the behind to work with and will take some trail and error to get right, good luck
Rob