Alternate possibility: religion is a pre-modern adaptation to encourage co-operation / unity / pro-social behavior and it likely correlated with fitness of societies for a long time.
To the extent it played that function, indoctrinating children was no different than teaching them to hunt or gather.