OMG is decimal that fast?
Maybe I should change the issue then to "documentation missing": it nowhere says in the documentation that decimal has optimized multiprecision computations. It only says that precision "can be as large as needed for a given problem", but I never realized that that included millions of digits.
It computed to my complete surprise 2**2**29 to full precision (161 million decimal digits) in about a minute. That smells suspiciously like FFT style multiplication, which implies that it is way more sophisticated than integer multiplication!
I suggest that the documentation of the decimal module recommends using decimal for multiprecision computations, as long as you use the builtin version.