If I were a sentient salamander, I might recognise genders/social categories based upon an individuals phase of metamorphosis, their current breeding potential, and perhaps if they have changed sex in the past.
Our hypothetical salamanders might undergo a life history where they are female transient when young and switch to male territory holder when old. This species when encountering us might insist upon gendering everyone as male after age 30 or when they buy a house.
I will bow to your expertise about salamanders.
The salamanders are extremely incorrect to try to map these concepts of what they know to us.
But you are somewhat incorrect to imagine there exists in nature a platonic concept of Male and Female that map very very well to Man/Woman.
I am not incorrect in imagining that, because I do not imagine that.