Does Time Machine have a separate phase just for encryption?
I assume you're backing up to a directly attached drive (USB drive or something similar)? When you select a local drive for encrypted backups, it converts the entire drive (or at least the volume you selected) to encrypted format, then starts backing up your data into it.

Basically, it's encrypting the current contents (probably most blank, but it encrypts blank space as well). Once that one-time conversion is finished, it'll start backing your data up, encrypting that as it goes.