So,
Kate and
Cate both have one syllable and the AY vowel by themselves, but using them as prefixes seems awkward because the "e" doesn't seem like it would change the A to an AY if it's in the middle.
When I see
Katelyn I know it's kate+lyn, but Catelyn is different though-- I never knew whether it was meant to be Cate+lyn or Cat-a-lin in ASOIAF until I heard it on Game of Thrones, and even then it seems to turn into Catlyn.
And I'd never read Catelina or
Katerina as Kate+lina/rina. Is
Katelyn just the exception because it's common enough? What about
Katelin? I'd assume that was kat-e-lin but it's not that different from
Katelyn.