I think that the Nonmen are too anthropomorphic for it to be a coincidence. They embraced philosophy sooner, so their society evolved faster than that of the humans. This kind of reminds me of the ancient Greeks. They also had a saying : "Πας μη έλλην βάρβαρος", which means every non Greek is a barbarian. Kind of how the Non Men see humanity.
There is also the fact that even if it's rare, it is possible to interbreed with humans, so their genetics must be extremely similar, implying a common origin. Add this to the fact that we know only about five tribes of Men, and the only other groups we know that could push that number to seven are the Nonmen and the Inchoroi and you can reach some pretty crazy conclusions.
[EDIT]
About the Nonmen magic points, the Gnosis is a tool that hasn't evolved for thousands of years. They are awesome with the Gnosis not because they have honed their minds with logic, but because as philosophers they have a natural affinity for the abstract. It's easier for them to recall their soul's past even if their brain can't store their own memories. Kellhus is a special case, since he has embraced both science and the abstract. He is conceptually (and probably even genetically) a hybrid.