you can create a category name with an apostrophe by using the html entity:
"Men’s Accessories" and "Women’s Accessories"
just be aware that if you edit the category name, it will display the apostrophe and you will need to manually convert it back to the html entity.