While the origin of the idea of a werewolf being literally haunted by his victims is hard to pin down, the condition of werewolf-ness, or "lycanthropy", is itself a form of punishment for the afflicted individual's actions. There is an excellent description of the history of lycanthropy on the Wikipedia page for "werewolf".
The earliest stories about werewolves come from Late Antiquity, and typically explained the condition as a punishment from the gods for some heinous crime, such as murder, cannibalism, or impiety.
From the wiki page:
The curse of lycanthropy was also considered by some scholars as being a divine punishment. Werewolf literature shows many examples of God or saints allegedly cursing those who invoked their wrath with werewolfism. Such is the case of Lycaon, who was turned into a wolf by Zeus as punishment for slaughtering one of his own sons and serving his remains to the gods as a dinner. Those who were excommunicated by the Roman Catholic Church were also said to become werewolves.
According to Armenian lore, there are women who, in consequence of deadly sins, are condemned to spend seven years in wolf form. In a typical account, a condemned woman is visited by a wolfskin-toting spirit, who orders her to wear the skin, which causes her to acquire frightful cravings for human flesh soon after. With her better nature overcome, the she-wolf devours each of her own children, then her relatives' children in order of relationship, and finally the children of strangers. She wanders only at night, with doors and locks springing open at her approach. When morning arrives, she reverts to human form and removes her wolfskin. The transformation is generally said to be involuntary, but there are alternate versions involving voluntary metamorphosis, where the women can transform at will.
In Hungarian folklore, the werewolves used to live specially in the region of Transdanubia, and it was thought that the ability to change into a wolf was obtained in the infant age, after the suffering of abuse by the parents or by a curse. At the age of seven the boy or the girl leaves the house and goes hunting by night and can change to person or wolf whenever he wants. The curse can also be obtained when in the adulthood the person passed three times through an arch made of a Birch with the help of a wild rose's spine.
So in the earliest tales of werewolves, one became a werewolf because of some evil deeds one had performed in the past; this may have gradually become the more familiar concept of a werewolf being haunted by its victims. The first well known portrayal of this concept was, as Victor has noted, Lon Chaney's role in the 1941 film The Wolf Man.
A more tragic character is Lawrence Talbot, played by Lon Chaney, Jr. in 1941's The Wolf Man. With Pierce's makeup more elaborate this time, the movie catapulted the werewolf into public consciousness. Sympathetic portrayals are few but notable, such as the comedic but tortured protagonist David Naughton in An American Werewolf in London, and a less anguished and more confident and charismatic Jack Nicholson in the 1994 film Wolf. Over time, the depiction of werewolves has gone from fully malevolent to even heroic creatures, such as in the Underworld and Twilight series, as well as Dance in the Vampire Bund, Rosario+Vampire, and various other movies, anime, manga, and comic books.
Thus, we see that werewolves have always been associated with a curse or punishment from the gods, and this, in itself, is a bit like being haunted by one's victims. It is difficult to track down the first instance of a werewolf being haunted, largely because werewolf stories, until very recently, were solely oral traditions, not frequently put into writing until about 3 or 4 centuries ago. We know that people have believed in lycanthropy for at least two thousand years, but we have very few written records of what, exactly, they believed about the subject until the medieval period. At that time, the concept of lycanthropy exploded into popular consciousness, and there were even trials of alleged werewolves.
However, for stories including the idea that werewolves are haunted by their victims to appear, it would first be necessary for the werewolf to become a sympathetic character, which, for reasons which should be fairly obvious, didn't happen until people no longer saw werewolves as a real threat. If you believe that werewolves are trying to eat you, you probably won't be especially concerned about them being tormented by the other people they've killed.