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 leave, to go away… or to die in some specific cases (“Il s’en est allé.”).

S’en aller is, to be specific, a relic. It belongs to the same family of verbs as s’envoler, s’enfuir, emporter, enlever, and a few others. Like these verbs, s’en aller (as well as s’en revenir, s’en retourner, s’en venir) has some features of fusion (notably that, as you both note, en is meaningless and can in fact be accompanied of a de-preceded object), but not that many. A good intermediate example is s’ensuivre, whose compound form, against all rules of French conjugations, is frequently built as s’en est suivi (these verbs are discussed by Grevisse in his Le Bon Usage §681).

The verb “aller” is based on three distinct latin verbs; ambulo/ambulare « se promener », eo/ire and vado/vadere « aller, marcher » : “Le lat. ambulare dont le sens était devenu « aller » dès l’époque class. dans la lang. milit., puis fam., s’est réduit,[…], plus prob. par l’intermédiaire d’une forme expr. de commandement militaire où ambulate « en avant, marche! » se serait contracté en a al(l)ate[…].” (TLFi; see also am/amb). “S’en aller” is generally a more intense form of “aller” and is ancient: av. 1188 pronom. « partir » (Parton., B.N. 19152, fo152 d, ibid. : Atant li dit : Vos en iroiz) (TLFi). As mentioned elsewhere, “en” can also be a pronoun (see pron atone 3e pers. i.e. tab 2), and it is here, and can be construed as representing an antecedent idea; it is naturally understood as what we’re moving away from (sort of like se aller de en) when used with “aller” in the sense of leaving (from). But grammar alone isn’t enough here.

With older French, many verbs related to motion were built using the reflexive+en (s’en partir, s’en monter etc.) and you also had an extremely rich use of the verb aller with the pronoun, including “en aller(à)” without the reflexive pronoun: “Atant est venus a ses gens, qui bien veoient qu’il ne revient pas si freschement qu’il en ala (ARRAS, c.1392-1393, 306); Finablement, le lendemain au matin en alerent a Charlon aprés messe (JEAN D’OUTREM., Myr. histors G., a.1400, 3).” (DMF). Conversely, you also had this case of “se aller” where you have the reflexive pronoun but no “en“: “Se aller. “Partir” : Et le duc le vit, sy luy dist : “Alons nous.” (JEAN D’OUTREM., Myr. histors G., a.1400, 148). …se ala et (…) feri ceval des esporons (FROISS., Chron. D., p.1400, 435).” (DMF) That is alongside a myriad of locutions leveraging “s’en aller (de qq. part/de lieu/devant/à qqn./devers qqn./après qqn./etc., see also Littré). Even up to the 4th edition of the Académie dictionary (1762), you still had something like “faire en aller” for “to make go away” something/someone. The Lacurne dictionary mentions that you also had inverted forms in the 13th : “Le verbe aller joint avec le pronom personnel, et la particule en, étoit réciproque. On disoit aller s’en ou s’en aller. « Comme elle se retourna pour aller s’en, elle se seigna. » (Vie de Ste Isabelle, à la suite de Joinsville, p. 178)”.

Another answer mentioned par. §681 of Le Bon Usage (Grevisse & Goosse, ed. Boeck/Duculot). To expand on that, the LBU explains that the pronoun “en” has lost its core meaning in “s’en aller“. The question is to what extent “s’en” and “aller” “stick” together as the more they do the less the pronoun means anything; the pronominal forms s’en aller, s’en venir, s’en revenir and s’en retourner, are provided as examples where the verb compound is not as tightly glued together (semi-agglutination) as it is with enlever, entraîner, emporter, emmener, s’enfuir and s’envoler where the pronoun is completely merged to the verb (this occurred in the 17th for s’enfuir and s’envoler). As alluded to elsewhere, the partial merging is further evidenced by the fact that another complement carrying the same value can be introduced with de, which tends to show that “en” no longer carries much value per se: “va-t-en d’ici!” (“leave away from here!”). This example with the imperative also shows that the compound can be split up to insert another pronoun (-t-; similar to when using tenses with a past participle: il s’en est retourné), which weakens its claim to a fully compounded verb construct; as does the idea that you can’t have two repeating “en” in a contemporary context. Nevertheless, very early on (12th), the pronoun “en” lost its meaning here, and the LBU provides the following example to illustrate (H8 note): “Li marchis s’en en ala en son pais.” (Robert de Clari, VI); you could have the pleonasm with the second “en” because the first one didn’t carry the idea of the originating motion anymore, so this is a specific instance where s’en aller behaves as if it were fully compounded even though it is not. We are then presented with three types of constructs for s’en aller: Il s’en est allé — Il s’est en allé — Il s’en est en allé. The latter two, built along the lines of il s’est enfui, are considered more literary yet appear in more casual types of documents. There is finally a mention of “en allé” frequently used as an attribute without an auxiliary verb, as opposed to en retourné and en venu which cannot do so without: Une âme en allée (Verlaine, Jadis et Naguère, Art poét.). S’en aller is a specific instance within a subset of cases where you have a partial merging of the pronoun “en” with the verb.

Grammatical analysis is not meaningless but it must also leverage the history of the language which, imho, supports both the meaning and the form of “s’en aller“.