Should I add new column or new table
The cardinality of 2  (male,female) is way too low.

Although you are using InnoDB and could have foreign keys, the parent table would have only two rows. It's not worth the processing power. Therefore, do not add another table. Indexing it is not worth it because a cardinality of 2 simply screams at the Query Optimizer "DO NOT USE THE INDEXES". Foreign Keys to a table with two values is not worth it.

Do not add a VARCHAR(1) because that is really two bytes.

There are four(4) options to use one byte


You could use CHAR(1) with 'M' and 'F' as the only values
You could use TINYINT with 0 for Male and 1 for Female
You could use TINYINT with 1 for Male and 0 for Female
You could use ENUM('M','F') (this might be two bytes)