Have you tried meshlab [1]? I've had pretty fantastic results reducing meshes from millions to some thousands.

[1] https://www.meshlab.net