"Frag" as slang for a kill in a multiplayer FPS game is about as old as deathmatch itself. Practically all id Software games use this term, going back to the original Doom multiplayer mode. From memory, Doom supported ending matches based on a "fraglimit," although I can't find resources for the "classic" Doom configuration/console commands to back up my memory.
I don't know that anyone has gone on record as to why the term "frag" was used. The original Doom didn't have grenades, so it's unlikely that it was chosen as shorthand for "fragmentation grenade."
It's possible it was related to the definition of "fragging" as killing of friendly soldiers. In support of this theory, in single player Doom the player faces off against enemies, usually aliens or some other hostile NPCs. In multiplayer deathmatch, however, human players are killing one another instead, making it more of a "friendly" kill than in the single player mode.
Another interpretation is related to the term "gib", see Wikipedia:
Gibs, short for giblets, is a humorous term referring to the variably-sized body parts ("guts"), fragments, and offal produced when non-player characters or game players are damaged or killed in video games.
With this interpretation, "fragging" your friends would mean reducing them to gibs (fragments of meat).