Phonemes exist. That’s one of the key findings of 20th century linguistics.
Where do they exist? In the Noosphere I guess; but they are mental constructs which underlie not only our articulation of language, but also our mental organisation and understanding of language. So unlike a lot that is in the noosphere, they do have a psychological, measurable reality.
Letters (Graphemes) are a means of capturing phonemes in writing. They’re some arbitrariness to them, but they definitely have referents with psychological reality. So they are signs, and they have as much existence as any sign in the world—that is, as much existence as numbers or words do.