Headlong evolved from Middle English hedlong, alteration of hedling, heedling, hevedlynge (“headlong”), assimilated to long. Headling in Middle English came from hēafodling in Old English and both of them meant an "equal/peer" or, previously, a "chieftain".
The head – yes, ancient people in Europe etc. correctly "guessed" that the mind is located in the head – has something to do with decisions. It can't be "a priori" determined whether the decisions are good or bad. "Headlong" means "without any detailed analysis". It means that the "head goes first" even though the head is the organ that should spend some time by thinking, and therefore go last!
Whether the negation is included in the head-based word for "recklessly" is a matter of coincidences. In Slavic languages, "headlong" may be translated as "without the head" – for example the Czech word "bezhlavě" ("bez" is "without", "hlavě" is derived from "hlava", a "head") is one of the synonyms equivalent to "headlong".
One might conjecture that the Germanic languages meant exactly the same (without the head, i.e. without careful enough of any thinking) but omitted "without" because the Germanic words for "without" are longer than the Slavic words (2 syllables instead of 1).
Update
The OP recommended me to add a reply to this comment of the OP into this answer:
Thanks. Would you please explain the apparent contradiction in It means that the "head goes first" even though the head is the organ that should spend some time by thinking, and therefore go last!? You appear to agree with me that the head should go last, because the head allows for thinking. So instead, in fact, why DOES the head go first?
I agree that when one is thoughtful, the head goes last, especially when the situation or act is truly dangerous or counterproductive. It's the other organs that go first and the head is the organ that says "slow down". In other words, the head "should" go last. That's exactly the reason why it is wrong for the head to go first – and why we think that it's reckless for the head to go first, or to go headlong or headfirst! Someone does something "headlong" when he's doing it the wrong way! So the word makes perfect sense.
This is just a rationalization of an answer. Our almost opposite "without the head" makes perfect sense, too.