How were hobbits created? I can't find any reference in The Silmarillion about this. Are they just men who have shrunken over generations or what?
From FotR ("Prologue: Concerning Hobbits"):
It is plain indeed that in spite of later estrangement Hobbits are relatives of ours: far nearer to us than Elves, or even than Dwarves. Of old they spoke the languages of Men, after their own fashion, and liked and disliked much the same things as Men did. But what exactly our relationship is can no longer be discovered. The beginning of Hobbits lies far back in the Elder Days that are now lost and forgotten.
So there is no absolutely definitive answer (consider them one of those mysteries and enigmas, like Tom Bombadil) but they are related to Men in some way.
The Hobbits were certainly related to the Rohirrim, as their languages share a lot of similarities. The word "hobbit" seems to have originated thus:(Appendix F)
Hobbit was the Name usually applied by the Shire-folk to all their kind. Men called them Halflings and the Elves Periannath. The origin of the word hobbit was by most forgotten. It seems, however, to have been at first a name given to the Harfoots by the Fallowhides and Stoors, and to be a worn-down form of a word preserved more fully in Rohan: holbytla 'hole-builder'.
lotr.wikia.com has a very good description of their history, which I will shamelessly copy and paste here:
Historically, the Hobbits are known to have originated in the Valley of Anduin, between Mirkwood and the Misty Mountains. According to The Lord of the Rings, they have lost the genealogical details of how they are related to the Big People. At this time, there were three breeds or tribes of Hobbits, with different physical characteristics and temperaments: Harfoots, Stoors and Fallohides. While situated in the valley of the Anduin River, the Hobbits lived close by the Éothéod, the ancestors of the Rohirrim, and this led to some contact between the two. As a result, many old words and names in "Hobbitish" are derivatives of words in Rohirric. About the year TA 1050, they undertook the arduous task of crossing the Misty Mountains. Reasons for this trek are unknown, but they possibly had to do with Sauron's growing power in nearby Greenwood, which was later named Mirkwood because of the shadow that fell on it as Sauron searched the area for the One Ring. The Hobbits took different routes in their journey westward, but as they began to settle together in Bree-land, Dunland, and the Angle formed by the rivers Mitheithel (Hoarwell) and Bruinen (Loudwater), the divisions between the Hobbit-kinds began to blur.
They probably just changed from the rest, like the Druedain.
Also, here are some quotes from The Letters of JRR Tolkien:
In the middle of this Age [the Third Age] the Hobbits appear. Their origin is unknown (even to themselves)† for they escaped the notice of the great, or the civilised people with records, and kept none themselves, save vague oral traditions, until they had migrated from the borders of Mirkwood, fleeing from the Shadow, and wandered westward, coming into contact with the last remnants of the Kingdom of Arnor.
† The Hobbits are, of course, really meant to be a branch of the specifically human race (not elves or dwarves) . . .
That confirms that the hobbits are essentially human, just a different (shrunken) variety.
I'd like to add some support to the general thrust of John Kevin Young's answer--i.e. that there was divine and/or magical intervention that either created the hobbits or melded them from other Middle Earth races-- by pointing to another frequently discussed mystery: Gandalf's seemingly offhand comment to Frodo in Fellowship that there exists "power of another kind" in the Shire.
My speculation is that hobbits appeared in Middle Earth around the time recounted in the Appendices but were simply too uninteresting for either Sauron or the Wise to take notice. I believe this was an intentional cloak of their creator (or creators--any of John's proposals other than Gandalf are possible in my view). Just as the Istari were sent by the Valar in overt opposition to Sauron, hobbits were a sleeper cell, unknown even to themselves.
They came to Gandalf's attention during the Fell Winter, and he studied them long, suspecting there was more to them than meets the eye.
Tolkien left it a mystery, like the origin of Tom Bombadil, when he could easily have provided an answer. This leaves the reader a lot more latitude to surmise the answer than Letter 131 might suggest.
As alsoskjjd points out, the physical differences between Men and Hobbits are far too great to indicate a common origin. Consider Australian Aborigines, genetically isolated for FIFTY THOUSAND YEARS, yet they are not a hundredth as different from other men as Hobbits are from Man.
Tolkien's suggestion should be taken to mean a cultural relationship to Men, because realistically, it's a big slice of Canadian bacon to say that they are just the result of genetic drift! Tolkien was an expert philologist, but he was not an expert at other things, including biological facts unknown when we wrote.
True, by the way, of all humanity's so-called geniuses; one may be a genius at one or a couple things, but never at all things. Mozart's opinions on economics are as worthless as Einstein's on the biology of yellow fever.
Besides, alsoskjjd's extremely telling point that if Hobbits were humans, they would not display such extraordinary resistance to the Rings of Power, is paramount. To take this point further, the existence of this singular trait in this singular population is, in my opinion, a clear indication of a divine hand in the Hobbits' creation. That is, the hand of a Valar, or Maiar or possibly the hand of a powerful being such as an elf or strange anomaly such as Tom Bombadil.
Where, then, did the race of Hobbits come from? I see them as combining traits of both Dwarves and in less measure, Elves. (In no way do I see them as little Men.)
Hobbits are the height of Dwarves, have feet that are far more likely from the Dwarf genome than anywhere else, and they dwell underground in holes. But modest holes in small hills, not grand caverns in mountains and massifs. Even their dwellings reveal no ambition or will to dominate others, which goes back to their near-immunity to the Ring.
As for Elven influence, while they are clearly not Elves (being mortal), they do have the ears, as well as an essential goodness as though they are of the Earth, but unlike Dwarves who are also of the Earth, untainted with that flaw of the bearded race, greed.
This point - that Dwarves have a fundamental flaw - is key to motivating the creation of Hobbits. Let me explain briefly that even before God ("Eru Iluvatar") created the first two races, Elves and Men, one of his Valar (like archangels), a smith named Aule, secretly created a race that he called Dwarves, fashioned from stone.
Aule being less than God, however, his creation was less than perfect. The Dwarves would lust for gold, and their physical appearance - stocky, low to the ground, lumpen-nosed - reflected this earthy fixation.
Now! - to use all these facts, I've come up with the bones of an origin story for the Hobbits along these lines:
A group of Dwarf families, perhaps refugees or exiles, came down the River Anduin from the north end of the Misty Mountains on rafts and were assaulted by Orcs. Knowing they were lost, they put their babies and toddlers in a small boat to escape, while remaining behind themselves to buy time for their wee ones.
The foundlings were spotted and rescued by someone who became more than fond of them. Through means we would call magic, this one, who was powerful, decided to heal the brokenness in them from Aule's flawed creation. (Oh, the things we do for love.)
The magic passed into the babes from above, changing their ears; and the Dwarvishness in them passed back into the Earth, changing their feet. Their bodies straightened and their faces grew fair and they stood now like Children of Eru, the first Dwarves ever to do so. So different they were that they were no longer Dwarves.
The Hobbits' ears, then, spoke to the magical grace that changed them, while their feet spoke to the former Dwarvish natures that left them with the gift of boots. And perhaps their greatest gift: they were now free from greed and the will to dominate others - the basis of their resistance to the siren call of the Ring of Power.
That's the basic outline. Now, as to the details:
Many elves dwelt along Anduin from the middle of the Second Age, Galadriel among them. Perhaps she is the one who found and healed them, both from love and from seeing in her Mirror that doing so might one day offer the only hope of saving the world that Eru had created. Such an action would then have to be concealed from the Enemy lest he hunt down and destroy them; concealed also from the Dwarves lest they be enraged.
Perhaps Gandalf (though not an Elf) visited and performed the feat of wizardry, or assisted, which would explain his continual infatuation with the Shirefolk and his dogged faith in them.
Their origin, by the way, had to have been farther back in time than their Third-Age emergence into history. The population size, and the existence of three distinct kinds of hobbit, points to an Age of multiplying and thriving quietly in three safe and isolated backwaters. Three is a sacred number to the Elves, supporting the role of Elves in the Hobbits' origin.
There are many ways this story can differ in detail. For instance, rather than protecting the Hobbits, the origin story may have been kept secret to protect the person who created them. In other words, the action that changed their nature and made them a new race was in some way questionable.
Perhaps the magical working involved the politics of the Valar themselves. Such an extraordinary change to Aule's creation might have required Aule's permission, or even Eru Iluvatar's.
Eru, after all, had forgiven Aule's transgression in creating a race of living beings, and he allowed them to awaken, albeit after Eru's own races.
Perhaps most intriguingly, maybe the origin of the Hobbits was the work of the two Blue Wizards, fresh from their supernatural life as Maiar (demigods) reborn in Middle-Earth in the bodies of old men. They arrived not long after Galadriel herself, and may well have traveled in the vast Vale of Anduin in time to rescue our boatload of babes.
The Blue Istari may have performed their actions as haplessly as Aule performed his, a god-like act and a breach of the protocol under which they were sent to Middle-Earth.
As a result, they may have suffered rebuke, recall, or exile, and were sent on their way Eastward, leaving the babe and toddler Hobbits with the Elves with no explanation - for shame - for what they had done. This is a particularly satisfying origin because it makes use of the Blue Wizards, whom Tolkien created but never did anything with other than dither over whether or not they ever did anything. :)
Being neither Elves nor Dwarves, the Hobbits were eventually provided the means to live on their own and the rest, as they say, is history.
It would clearly take a novel to tell this story properly. :)
I do hope this at least provides some food for thought in answer to your question, and an alternative to the (to me) boring and unsatisfying idea that Hobbits are no more than an offshoot of Men, developed in some swamp through deviancy and inbreeding (cue the banjos). And yet with a core of Good at their heart, like an Arkenstone, for no reason at all. (Maybe incest really IS wincest?)
There's no magic in that notion. Hobbits are not, and cannot be, Mini-Men!