Descartes' genium malignum or malin génie is not an 'evil genius' but a 'malignant demon'. Genius doesn't come into it. Also Descartes does not actually psychologically doubt the existence of the external world and the rest. Since he accepts that he can be mistaken about them, he voluntarily suspends epistemological judgement about them. He practises methodological doubt, and puts methodologically 'on hold' any belief which is not invulnerable to error. Complexities aside in Meditation 2, any belief which passes that stringent test is one he can allow into his construction of the foundations of knowledge.
In his Comment, Bread has got to the root of the matter. 'Our minds' plainly exist if the malignant demon has planted doubt or doubts into them : doubt can't be created in a mind that doesn't exist. More broadly, if the demon has caused me to doubt, psychologically or methodologically, then even if I don't know what has caused my doubt (actually the demon), I must exist in order to be caused to doubt.
There is the point, of course, that my belief that even if I am deceived, I must exist else I could not be deceived, might itself be a false belief induced by the demon. I don't know how to deal with that, but it takes us (I think) beyond the limits of your question.