Well your question here stems from a rather present-ist point of view; namely lumping together all supernatural beliefs (and for that matter, identifying them as such) as mythology and then holding that in opposition to Christianity as a different religion.

But the average 'pagan' didn't see things that way. Belief in elves/fairies wasn't necessarily seen as any different from believing in the existence of, say, bears. So when Christianity comes along and says you should worship the Christian god, and these other gods are false - why would that change your view of elves? Christianity does not deny that strange creatures exist; the Bible contains a fair share of them, such as giants (Nephilim) and a sea monster (Leviathan).

Already before the Anglo-Saxons converted, some theologians had explicitly explained certain Greco-Roman creatures in a Christian context, notably Saint Jerome in the 4th century (in Life of Paul the Hermit) declared that Fauns, Satyrs, and Incubi were an actual desert creature of a mortal variety who'd formerly been worshiped in error.

That, and many other examples of monsters were listed by Saint Isidore of Seville (6th century) in his Etymologies, which was very influential through the middle ages and approximately contemporary with the conversion of the Anglo-Saxons. That's not to say all supernatural beings were accepted either, though; Isidore lists a number (e.g. Sirens) which he claims do not exist. It's just that the criteria here was how these creatures fit into the Christian world-view, not simply whether or not people had believed in them before conversion. If a belief (e.g. Norse giants/jötunn) could be justified from scripture (e.g. Genesis 6:4) then Christianity just verified the belief. Whereas if the belief was at odds with scripture then clearly that'd been a false belief.

Elves too would (to an extent) be fitted into such a framework; Chaucer would (far after Alfred's day) equate them with the aforementioned Incubi. Bald's Leechbook, contemporary with Alfred, lists several remedies against Elves, implying they could curse or otherwise do something detrimental to people.

The term 'ælf' was also used on occasions as glosses (explanations of difficult words) in Old English for terms in Greek sources such as nymphs and dryads.

From Norse sources (which may not resemble much what the Anglo-Saxons had believed centuries earlier) we have Snorri's distinction between light and dark elves, which may have been inspired by Christianity. The Scandinavians also sacrificed to them on a regular basis in a named religious occasion (álvablót). On the other hand the concept was not so sacred that people weren't named that; besides Alfred you have Ælfwine (elf-friend), Ælfgifu (elf-gift) and so forth, and in Scandinavia simply Alfr (elf) and Alf in later form, which continued to be used from at least the Viking Age, to after Christianization, through to present day. Unlike god names like Thor and Freya which did not exist as personal names in the Viking Age. Belief in elves continued as well - in a sense - although the älvor one finds in modern Swedish have by the 19th century little more than the name's etymology in common with the Old Norse elves.

Belief in elves - in a changing folkloric form - also continued in England through the Middle Ages and even longer in the north and Scotland.

So I don't think it's really possible to nail down what the meaning of 'elf' was in these names, because the sources we do have give a rather contradictory image and don't date from when the names were first coined. The names could well continue to be used even as the meaning of 'elf' changed over time. (making them 'fossil words')

For instance a name like Torbjörn (Thor-bear), which is still popular today, must've originally had a ritual/religious significance. But for most of the past 1000 years it's simply been used by people who liked the name, with no regard for any of that.

On a side note when and why did names that started with 'Æ' (Æthelred, Æthelwulf, Æthelstan etc.)

You're missing a verb here?

In any case all those particular name start with the same prefix (Æthel = noble , c.f. German 'edel', Swedish 'ädel' etc) If you're asking when the æ went, it largely vanished as Old English became Middle English.