Thanks for posting that. I confirmed that it was very slow and had a look at the code. I was able to make some optimizations to the code and make it a lot faster.
It still took over an hour to reduce the 1.4 million triangle model down by 50% but subsequent reductions were much faster. I ran the 50% reduction a few times and the results are in this file - the smallest version I did has 87k triangles and it still looks good. Further reductions should be fine, speed wise, on the current AC3D.
http://www.inivis.com/external/test/Medusa_reduced.zip
These changes will be in the next release.