Female has its origin in Latin and comes from the Latin word "femella", or "femina", which of course means "woman". Male, on the other hand, come from Old French "masle", or as we know it in modern French "mâle", that itself comes from the Latin word "masculus", both of which mean "male human". Over time "masle" became Male and, around 14th century, after a long use side by side with Male, "femella" morphed into Female, bringing both words in line with the modern usage. There is no prefix Fe in the word Female, Female stands on its own, and only after centuries of misspelling did the words Female and Male acquire their similarities.
Woman and Man are little bit trickier than Male and Female. Man obviously is the root, but the problem is that the word Man used to mean "person" or "someone", and was gender neutral. You could call anybody a man as long as they were human. Man is derived from Old English "mann", or the earlier Proto-Indo-European word "mon" (or "man"). So when you joke that in the good old days men were men, women were men, and children were men, you are kind of correct. In Old English the word for Man (male) was "wer" or "wǣpmann", but it disappeared around 13th century and the word "man" took over, although it still could be used in gender neutral sense and did so all the way to the twentieth century. Old English word for woman was "wif" or "wīfmann". "Wif" obviously turned into modern "wife" and "wīfmann" became the modern word "woman". So you can say that Man and Woman have the same root, Man, although it means a human or a person rather than a male
