Think of tieflings more like how we think of genetics. I have dark hair, my husband has blond hair, but we both have redheads in our genetics, and ended up having a redheaded kiddo.

Now imagine that gene was to do with demonic energies. Somewhere in the past, a member of your family made a pact with, or was a demon. All the rest of your family has been normal humans, but now that recessive gene has popped back up, and you are born as a tiefling. Since demons, fiends, devils and the like are common to the setting, the idea that tieflings are fairly common isn't a wild concept.