The prefix de- does not necessarily mean "away." Etymology online says:
usually meaning "down, off, away, from among, down from," but also "down to the bottom, totally" hence "completely" (intensive or completive)
Note in particular the second portion of this. Thus, a possible explanation is that the de- was added to the Latin fallere as an intensifier, indicating complete deceit or failure. This doesn't explain why EO glosses de- as "away" in its explanation, but it's one way to explain the etymology.
The OED, in its discussion of the de- prefix in English, mentions several Latin words that had the prefix de- as an intensifier:
- deplorare, to weep as lost
- despoliare, to spoil utterly
- declarare, to make quite clear