My theory is that the Cycle doesn't begin with a natural, millenia spanning evolution, but rather some supernatural creation. After all, if the middle part of the Cycle (the rise and fall of the false gods) can be controlled by a supernatural entity (Sarantha, or Fate) and the ending part (the Cleansing) as well (by the High Ones), it sounds logical that the beginning of the Cycle (creation of life, maybe all the way up to the fall of the first civilization) would also have some supernatural entity controlling it, thus making the appearance of life happning in centuries or millenia, rather than in hundreds of millions of years.