When the the government decided that Native American could finally become citizen of You Ess of Aye in 1924, they sent census people to the reservations to account for all the Natives. It is here that English names and surnames were given out - some randomly and jokingly. Some were spared humiliation - in that Native names were translated: thus, Blackhorse, Grey Eagle, Yellowhair, etc. other names were Anglicized: Begay is one of those names. In Navajo - Begay is "Biye'" meaning "his son" or "son of" - so for instance: a census person asks a young Navajo guy what his name is - and all Navajo have been taught that the given names are sacred and to give that out is sacreligious, so they had other common names - so the young might say: Hastiin Tso Biye - meaning, "Big man's son", so the poor guy says, okay, you'll be John Begay (since Begay is the closest he could get at Biye' in English). So that is how Begay - in Navajo - came to be.
Sorry I do not know the story behind the Ukraine Begay.