How does “be” as a prefix work with both the words befriend and behead?
Befriend means “become friends, having a friend, thoroughly or completely friends”
Behead means “without a head, to lose your head, thoroughy or completely take off ones head”
Looking up the definition of the prefix “be” it seems more fitting in the befriend example.
How can it mean “to gain” and “to lose” at the same time?
How does it make any sense in the behead example?
Well, “behead” is a transitive verb. When you behead someone, you don’t lose your own head; they lose theirs. So, in a sense, you do gain a head.
But maybe the explanation is just that the same prefix/syllable can have more than one meaning. (As in, “the firefly was delighted when he backed into the electric fan.”)
Nice question, but AFAICT, the ambiguity goes back to Old English, so it’s no use expecting them to fix it now. 
The prefix “be-” is from Old English “be-, bi-”, meaning “by”, in the sense of both “close to, nearby” (also as a general intensifier), and “separate from, not part of”. It also turned adjectives or nouns into verbs: “befriend”, “bespectacled”.
So if you’re “bedecked” or “beset”, you are closely or intensively decked or set: it’s all around you, right by you. But if you’re “beheaded”, your head is by you, next to you, not part of you.
Bewildered means wildered and befuddled means fuddled.
Yup, that’s the “be-” prefix acting as an intensifier. It slices and dices too!