It's funny, I've never seen any description of how it arose. Historians seem to almost treat it as autochthonous.
It actually seems to have had close parallels in most Italic and Etruscan city-states we know enough about to guess, that is, usually South Etruria and Campania.
An Etruscologist whose name I forgot, and whose work I read recently, interprets the system of Roman clientage as an extreme within the spectrum of social dependence typical of all Mediterranean city-states of Iron and Classical age: Rome and Sparta likely represented the extremes, with clientes and helots being respectively the freer and less free among these non-slave dependent groups.
Roman clientage also appears to have been rooted at least in part to "Indo-European" ideological notions (the dependent retinue of a noble house with mutual, but unequal, obligations - there are known Celtic and Germanic parallels, though I am sure that a lot of this is not limited to IE speaking societies).
So yeah, it's hard to image a more basic institution in Republican Rome.