Many modern fantasy stories heavily feature the idea that the strength of a god is proportional to the number of their worshippers. This is reflected in the real world, as the strength of a religion is generally proportional to the number of its worshippers - although this varies depending on their militancy and their outspokenness. Another visible mark of "worshippers" in older pantheons of gods (I'm thinking mostly of Norse and Greek) is how many stories a god has about them: Loki is a trickster and a great person to create a story about, so more stories are told about him. Then more people remember/believe in/worship him.
I think the idea of strength in ratio to number of worshippers first came to my attention in Terry Pratchett's Discworld novel "Small Gods" (1992). The book centres around the "Great God Om," who finds himself manifested in the world as a small tortoise and with no godly powers. This is because he has only one remaining worshipper, a man by the name of Brutha. To regain his powers, he and Brutha must convince people to start worshipping him again. It's a concept that Pratchett carries throughout the Discworld series, with gods both large and small depending on their worshipper base.
Most recently in my reading, we have Three Parts Dead (2012) by Max Gladstone. Three Parts Dead was the first book in "The Craft Sequence," and the idea is used throughout the five books. Gladstone makes the distinction between "belief" and "worship:" the gods DO exist, and they're powerful and dangerous - so it would be silly not to believe in them. But they're only powerful in proportion to the number of worshippers they have.
So did the idea start with Pratchett? He was a very smart man, but he wasn't above borrowing a good idea either. And, while I do read some fantasy, I'm better read in the science fiction department and couldn't really say. It has to be a relatively new idea: to publicly state such an idea more than a century ago would be to invite charges of blasphemy and a possible death sentence.
One gentleman (a patron, not a staff member) I spoke to at the Merril Collection of Science Fiction, Fantasy and Speculation suggests that the idea dates as far back as the Norse Eddas (13th century, Iceland) - with the Norse God's strengths waning as their people turn to Christianity.
- "The Sandman" by Neil Gaiman (1989 onward) - the origin of this series of comic books predates Small Gods, but 1) may not predate Pratchett's use of the idea, and B) Gaiman's use in this series (as I remember it) may have post-dated Small Gods anyway. The cat goddess Bast draws strength from the number of cats who remember her. There may well be other examples. (Gaiman and Pratchett knew each other well, once writing a book together - the excellent Good Omens.)
- "American Gods" by Neil Gaiman (2001) - thanks to Matthew for reminding me.
- "Anansi Boys by Neil Gaiman (2005) - thanks to Sheilah for pointing out this semi-sequel to American Gods.
- "Supernatural" TV series (2005), which has gods and the premise that belief is power. Thanks Marni.
- "Stargate SG-1" TV series (1997-2007) - thanks to Ian, who says the idea showed up "toward the end of the series."
- "Gods Behaving Badly" by Marie Phillips (2007) - the Greek gods are all alive and living in modern London, but they're essentially powerless because they have so few believers. If they had more believers, they'd be more powerful. Phillips' gods rely on "belief" rather than "worship" - an important distinction that takes choice out of the hands of the mortals.
- "Clash of the Titans" (2010) - in this movie Hades releases the Kraken, knowing that it will weaken the other gods (but not him) as it kills their human worshippers.
I hope to update this as people suggest other titles.