My relatively uninformed guess is that it is likely caused by Cycles shader optimization, or in this case the lack thereof.
Textureless volumes are probably assumed to have constant color or density, and as such optimized to render disregarding variations across the smoke depth.
This probably saves considerable processing power by skipping color or density checks at every depth step, as the rendering rays traverse the volumetric shader.
It may also be the case that by using heat as input into your shader, Cycles requires more data that either consumes more (system or GPU) memory, or requires uploading CPU computed data from the smoke simulation into the video memory (when GPU rendering using CUDA or OpenCL) at every frame, which is generally a slow process.
After a simple test I'd go with the theory of shader optimization. Just having a simple color input like texture coordinates on a basic volume shader almost duplicates render time.
Constant color about 15 seconds
Simple color variation about 30 seconds
I guess a smoke simulation with varying density and heat based colors will only worsen the calculation.