I'm not quite sure what you're asking here. Are you looking for a way to come up with exotic species or with how to convey their presence without actually showing them?
If it's the later you could try this environmental storytelling and the use of stories within stories. Thomo already mentioned this and it's also something Tolkien did amazingly well.
You can have people tell stories to your character. You can even make them third hand, kinda like "My father once knew a miller who said that one of the cart drivers who delivered the grain to him once saw a company of elves during one of his travels... Strange fellows they where, he said. He couldn't quite see them through the leaves but they where tall and white and glimmed with an eerie light even in the dark of night, I tell ye. And they was singing a song more beautiful than any woman can sing under these here heavens!"
Then there's rare artifacts. "Do you see these runes? This blade was made in the splendid smithies of the dwarves of Coal Mountain over a hundred years ago! Look, it's still as sharp as if it was newly forged! This is a rare treasure you have here.".
Then of course, ruins help. "The stones where mostly overgrown with ivy and moss but one could, with some effort, still make out the dimensions of these once great halls. Nearby was a crumbled statue of an elf lord of sorts. It must have stood 10 feet tall before it fell. Carl wondered if elves had really been this tall. The face of the statue was unnaturally slim and the ears ended in long, slender tips, almost as long as his fore arm. The eyes were slit-like and dark. Imposing creatures they must be, these elves!" (Of course the statue is a stylized version of an elf but Carl - not knowing anything about the elven art style - doesn't realize this and takes it for a realistic depiction)
Then there's of course bards, messengers and other far-traveled people. In the middle ages this was how news would travel. Bards would often earn their living by telling stories and singing songs from faraway places where they had been during their travels.
Veterans could talk about this war that they fought five years ago in the far reaches of the western plains where they fought an army of Yrch and how they still have nightmares about it, proudly displaying their scars for a mug of wine.
You could have maps where the far reaches are sketchy and labeled "Elf Land" or something.
In the big cities (probably where the king resides) there might be the odd "outlander" on a diplomatic mission. In cities with big markets on important trade routes you might find a handful of elvish traders, offering exotic wares.
As these things go, it's always informative to look at material about the middle ages. The book Pillars of the Earth by Ken Follet illustrates it well, but it is a massive tome and the part where he talks about how the islamic and the christian world learn about one another and how information travelled across Europe is just a comparatively small part of it. It's quite a good book though and definitely worth reading if you have the time. Not for the faint-hearted though. And of course, reading Tolkien is always instructive.
Creature design is a different topic though and probably fits best into the Worldbuilding SE.