This goal of this post isn't to define RPGs. Rather it's to provide a categorical survey of defining characteristics, as suggested by various observers.
First note that all games except a very few have elements of freeform, and even those that don't still have a fiction; otherwise, they are merely (virtual) kinetic art. (By the first I mean, very few games tell you precisely what to do at every step. Chutes and Ladders does. Chess and Monopoly do not. By the second I mean that the game proposes a set of meanings--often the concept of "winning and losing"--that have no real impact outside the game.)
So what is an RPG? What distinguishes it from other games? Markus Montola has proposed some criteria for roleplaying. An earlier discussion on rec.games.frp.advocacy also comes to mind.
Lea Crowe wrote:
Specifically, I think, a wargame does not concern itself with "literary" issues: character, plot, mood, etc. In a wargame, the action is all. 
This may be a side point, but in the majority of (modern) wargames, action is delimited by the rules, rather than merely being guided by them. For example, you can only use the tactics of spying, seduction and assassination if there are rules for them -- you can't just come up with a "spy" unit, any more than you can arrange a Mafia hit on someone in Monopoly. 
Lea's first paragraph refers what I'll dub the thematic or aesthetic criterion. It's been a problem for RPGs for a long time. Arguably this criterion underlies GNS (in the sense that aesthetic goals are what GNS is about instead of formalism and procedures). It's also related to some of Markus Montola's criteria.
The second paragraph is the freeform procedure criterion. I think this is a weak criterion for RPGs but it's advanced frequently. Essentially it's the criterion which says that the vision of the world overrides formal rules, or rather the vision of the world and how it can be acted on by the players cannot be encapsulated in formal rules.
In response to Lea, I added:
--Wargames generally have unambiguously defined "victory conditions" as part of the rules. RPG's generally don't. 
--Wargames have well-defined conditions for when the game ends. RPG's generally don't. 
The third criterion, which I proposed, is the motivational criterion. The claim here is that RPGs do not provide clearcut purpose, within the game, to guide player "moves". Consider: tennis, within the game, is motivated by scoring points and winning the game/set/match. (The goal of winning the match might conceivably override the goal of winning the game. As e.g. if you make shots which your opponent can score on provided he or she exhausts herself. But there is a unitary goal guiding your strategy, tactics, and technique/skill.) Outside the game, tennis may be guided by things like trying to impress someone on the sidelines or not making your boss look bad. But the goal is in the fiction of the game and the metagame goals are achieved via the game fiction.
By this criterion, an RPG explicitly does not have a formal goal in the fiction. I think this is an essential criterion, but it is sometimes excluded (generally only provided freeform criterion is satisfied; otherwise you have a closed system that becomes boardgame-like).
The fourth criterion, above, is the endgame criterion, but I think it's been basically disproved. At most it's a special case of the third criterion. Nevertheless it's still expected by many that RPGs will either go on indefinitely, or end only when some non-formal condition is reached, such as general agreement that all the "story arcs" have been played out.
[The rest of this post remains highly sketchy. Sorry.]
Now compare: pictionary, charades, the imagine-a-journey game, etc.
added: note that I don't use the word role above. So let's read what Jonas Dagar has to say about "not an RPG" and Wittgenstein. I find it very exceedingly useful to imagine that "these games" are not being called "RPGs" or even "storytelling games". These terms imply motivation and may (1) constrict play and (2) give a designer an excuse not to really explain their game. Charades doesn't have that problem. Nor does Werewolf. So what are "these games"?
Also look at this rpg.net thread about Capes.