I tried it with both sides on deity. Standard conquest seemed like a valid option. Apparently you don't even have to build the temples, just killing Egypt/Nubia will do the trick. So many clicks and turns wasted on building holy sites and such

Oh well, didn't bother with those in the second run. Just spammed units and the occasional commercial hub to avoid bankruptcy.
Playing as Egypt was kind of tedious, though. Even when Nubia had only one city left, she seemed to spawn something like 4 swordsmen and 2 pitati archers every 3 turns

Also, it really sucks that the great generals can't be killed.