WordPress: combining category and tags

I’m building a E-commerce site that have a category for men and women’s shoes.
What I want to achieve is make a group for all the brands( men and women ) and group for gender specific shoes.

ex.

men > nike, addidas, converse
women > nike, addidas, converse

AND

"Nike > shows all content for men and women"
"Addidas > shows all content for men and women"
"Converse > shows all content for men and women"

I’ve read a few articles about it and it suggests that I rename the brands into sub categories like. (men’s > nike_mens, addidas_men, and so-on) the problem is it will lack the function to retrieve a specific brand that displays all shoes for men and women. And then I found in another post that you can make a tag for gender but I tried to do some experiments on it but I was only able to retrieve all categories or all tags maybe there’s a way to join those 2 taxonomy to produce my desired result without hindering performance.