A "fell beast" is not a specific type of animal. "Fell" is a somewhat archaic work meaning "fierce", "deadly", or "terrible" -- basically, pretty any dangerous animal can be a "fell beast."
In LotR, Tolkien uses it twice:
Under the boughs of Mirkwood there was deadly strife of Elves and Men and fell beasts.
Could be pretty much anything, really. Wolves? Bears? Spiders, even, though "beast" usually means a "mammal."
But thereupon Éomer rode up in haste, and with him came the knights of the household that still lived and had now mastered their horses. They looked in wonder at the carcass of the fell beast that lay there: and their steeds would not go near.
Here it's the flying reptile that the head Nazgûl was riding.
Where did they come from? It looks like they were already around and Sauron gathered them in. (You'll remember that the events of The Hobbit were set in train because Gandalf feared the Sauron would find a way to use Smaug (no creature of Sauron's) against Elves, Dwarves, and Men.
Among many cares he [Gandalf] was troubled in mind by the perilous state of the North; because he knew then already that Sauron was plotting war, and intended, as soon as he felt strong enough, to attack Rivendell. But to resist any attempt from the East to regain the lands of Angmar and the northern passes in the mountains there were now only the Dwarves of the Iron Hills. And beyond them lay the desolation of the Dragon. The Dragon Sauron might use with terrible effect.
So, as Gandalf says:
'Alas! Mordor draws all wicked things, and the Dark Power was bending all its will to gather them there.
Sauron pulled in "naturally occurring" beasts (many fashioned by Morgoth, no doubt) and perhaps made them more dangerous.
Going earlier to The Silmarillion, Oromë the Vala is
...a hunter of monsters and fell beasts, and he delights in horses and in hounds;
In Beleriand, Dwarves reported that
'There are fell beasts ...in the land east of the mountains, and your ancient kindred that dwell there are flying from the plains to the hills.'
And ere long the evil creatures came even to Beleriand, over passes in the mountains, or up from the south through the dark forests. Wolves there were, or creatures that walked in wolf-shapes, and other fell beings of shadow;
Later, Sauron apparently added malevolent spirits to ordinary wolves:
Therefore and army was sent against him under the command of Sauron; and Sauron brought werewolves, fell beasts inhabited by dreadful spirits that he had imprisoned in their bodies.