It's an idiom. Lots of idioms don't make sense if you try to analyze the literal meanings of the words. Yes, "head over heels" makes no sense. Most people normally sit or stand with their head over their heals.
But one could say similar things about many idioms. Consider, "I could care less", which means that I don't care. But if you could care less than you do, doesn't that mean that you DO care? It would be more logical to say, "I couldn't care less."
Or less blatantly, "Something came up." As opposed to what? Something came down? I heard a joke once where a foreigner trying to learn English is invited by some friends to go out to a bar after work. He says, "Sorry, I can't go, something came down." His friends laugh and say, "No no, the expression is 'something came up'." Puzzled, he replies, "Something came down. Wife's foot."