3 of 4 added link from comment

The Zohar writes that the Patriarch Yitzchok had the soul of a female.

Additionally, the Arizal explained that Michal wore tefillin because she had a male soul.

So it seems that souls do have genders, both male and female.