Alan sees Mary standing at the other end of the bar. He goes (over) to her and says "hi".
Would it sound odd if I didn't add "over" in this sentence?
Yes, without the "over" it sounds odd.
I can't quite put my finger on why. Just plain "goes" suggests (to me) a kind of directness that would be inappropriate in a casual bar get-aquainted scenario.
If Mary were the suspect in a murder mystery and Alan the detective, his seeing her would have some implications, and he might then just go to her. That would be the case too if they were a couple.