Anatta is often described as "not-self" which I understand to mean that our identities are illusions.
No, in fact, the meaning of not-self, as others have pointed out, is that the object in question is not self :) The Visuddhimagga offers some good explanations:
All that [materiality] is “not-self in the sense of
having no core.” In the sense of having no core because of the absence of any core of self conceived as a self, an abider, a doer, an experiencer, one who is his own master; for what is impermanent is painful (S III 82), and it is impossible to escape the impermanence, or the rise and fall and oppression, of self, so how could it have the state of a doer, and so on? Hence it is said, “Bhikkhus, were materiality self, it would not lead to affliction” (S III 66), and so on. So this is also not-self in the sense of having no core. Accordingly, there is one kind of comprehension in this way too, but it is effected in eleven ways. [611] The same method applies to feeling, and so on.
and
There are twenty-five kinds of contemplation of not-self by taking the following five in the case of each aggregate: as alien, as empty, as vain, as void, as not-self.
You say:
But it's also described as "soullessness" which I think implies that there is no mind other than the brain itself.
Absolutely not! The five aggregates are non-self, four of which are outside of the domain of the brain.
If there is no soul, how can there be rebirth?
There isn't in fact any such thing as rebirth, in ultimate reality. Nothing is truly reborn, ever. Every experience that is made up of the five aggregates arises and ceases without remainder. That is true death. Rebirth is a concept used to describe the change between one artificial framework of experiences (e.g. a human life) to another. The ultimate reality is that the mind simply arises and ceases at the last moment of life and then a new mind arises at the first moment of rebirth based on the last one, very similar to as has been occurring throughout one's life, except this time there is no old physical phenomena for it to be based on, so it is based solely on one's final state of mind in the last life.
Here's something that might help:
https://www.youtube.com/watch?v=XClIR19eufc