Specifically, assuming a succesfully policed border, how did one prove their nationality, if they had such a thing, or their legitimacy otherwise for crossing it?

I will take your word for it either way! Just genuinely curious. How was it all handled before passports and birth certificates and such?

For identity away from people that knew you or your relatives you had to rely on physical letters of introduction from trusted, well know people.

But usually you were proving that you were entering (or leaving) for a legitimate purpose rather than identity exactly. There is a long history of travel documents for this, see https://en.wikipedia.org/wiki/Passport#Antecedents

Worth noting that once urban centers formed travel became the exception rather than the rule. There were traders who traveled trade routes and knew that requirements on those routes but for more exceptional travel you had to rely on these introductory letters in many areas of the world.

Mass migration events were different of course - and were always problematic.

The concept of a passport didn’t emerge out of the ether. If you were traveling on official business, for the state or the military or as a merchant, you’d be carrying papers that said as much. Much of it relied on trust and reputation, and assuming we’re talking about say medieval Europe possibly the signature or word of a Lord. As for enforcement, violence was common.