I think tribalism might be rooted in embarrassment.
You can see others' sins much more easily than your own. When you go to the next tribe over, you can see how they low-key hate each other and act accordingly. "At least I'm not like that!" Problem: a sneaking suspicion your tribe is like that too, because it is. However, you have scar tissue and callouses from being needled in your tribe's characteristic way, so there's a chance of drowning it out. Every time you see the foreigners, they remind you again of how you're not as good to your friends as you say you are, which inspires another round of tribal signalling attempting to drown it out with dissimilarities. With frequent contact, it gets well out of hand.
A human species that wasn't by default territorial and xenophobic would inevitably become xenophobic.
Not to mention that different cultures really do clash. Differing assumptions cause an interaction isomorphic to a computer crash. Pass variable A, it is taken for variable Q. Error, divide by zero.
However, if embarrassment is a driving cause, then xenophobia is mainly a manifestation of self-hatred. Autophobia. Hence the desperation involved in pushing away foreigners and heretics. No confidence.