The kanji for かれ is 彼(れ). かれ is an old form of あれ, meaning "that one" (as you probably know). 彼 can also be used in [彼]{あ}の (again, "that one [specific thing]"). Somehow -- and I'm not sure how etymologically -- 彼れ became 彼, which became shorthand for 彼の男: that man
The kanji for 彼女 is then basically [彼]{あ}の[女]{おんな}: that woman (again, with the かの being an old form of あの and the の being omitted). See more about this explanation here: What does かの日 mean?
These words also became shorthand when talking about relationships (boyfriend/girlfriend), but I don't know about the etymology of this either.