This is totally doable. Rather than viewing it as “two product listings” just view it as a single product that is multiple collections or having both “mens” and “womens” tags (existing shop configuration will determine the best option in using tags vs collections).
With collections, you can define automatic collections that will automatically populate with products based on selected parameters. You could for example create a “unisex” tag, and then set the “mens” and “womens” collections to automatically add all products with the “unisex” tag.
Let me know if you need further clarification on how to accomplish this
Edit: I see that you also want to dynamically change the name based on category. I missed that previously. This isn’t possible without some editing of liquid template files. Totally doable, but it would take an hour or two to code and test the solution across multiple template files.