First, en is not only a preposition like in:
Il parle en mangeant.
Il arrive en France.
it is also a personal pronoun. In the following example, it refers to an indefinite amount of something:
Du chocolat, j'en mange beaucoup.
Or it can be an adverbial pronoun. For example to refer to a place:
L'aéroport ? Justement, j'en viens.
But it's also a word that is used in many locutions.
In your sentence, it's part of s'en aller which is a verbal locution. The meaning of locutions cannot be inferred from the meaning of isolated words, and sometimes they break standard grammatical rules: in this case the en is dangling, it refers to nothing specific. Also, the “s' ” is a reflexive pronoun and it must be inflected in accordance with the subject:
Je m'en vais.
Tu t'en vas.
Il s'en va.
Nous nous en allons.
etc.
The fact that the reflexive pronoun appears is specific to this locution and cannot be understood. As you mentioned, the verb aller can't usually be used reflexively: *s'aller is not French. (Saler does exist, but it's something different ;-))
As for the meaning, s'en aller often means to go away… or to die in some specific cases (“Il s'en est allé.”).