Once upon a time there was the Latin word "locus", meaning "place", which had various different declensions, but somewhere along the line in the vernacular in the areas conquered by Rome it had a strong tendency to shift towards something that dropped the last syllable (so "loc" instead of "locus") and then fucked around with the vowel in all kinds of directions.
But then the speakers of Gallo-Romanic dialects went even further and they got rid of the "k" sound entirely and started just saying the l and the vowel, which eventually got us to the Old French "leu".
Now the thing is, right, that in the old languages the spelling is very much a sort of consensus thing. It's not perfectly phonetic, because it can't be: all of the languages in question had phonemes that weren't exactly the same as the Latin that existed when and where the Latin alphabet was formalized, right? So as people wrote down the Old French vernacular, they basically took the letters they were taught and they used them to represent the sounds they were making.
This happens with all the languages; there's a really neat thing where if you look at Visigothic manuscripts, writing in the area that would become Spain and the vernacular form that would eventually be Spanish, you can see the difference between the sound of "v" and the sound of "b" disappearing, so that there are manuscripts where "Ave Maria" is written "Abe Maria", because to the people reading it, b and v made the same sound.
This is relevant to the question because of a fun little fact about mediaeval orthography! Which is that the characters that we now feel are absolutely separate, different letters - that is u and v - were both used for both sounds. It's not that "u" and "v" were the same letter exactly - they weren't - but that the character you used was the same and which you used depended more (properly) on where in the word the letter came, than which one it was.
So the word "hut" would indeed be written with "u", but the word "university" might well be written "vniuersity".
But it gets worse from here, because the sound of the letter we now call "v" and the letter we call "f" were also often used interchangeably. So it might actually be written "vnifersity".
If your eyes are crossing, remember that we still randomly stick "qu" in places to be "kw" and there's quite complicated rules about when the character "c" says a hard back of throat sound the same as the letter "k" and when it says a soft sibilant like "s" and also sometimes when it does something completely different.
Now as it happens the point of writing is to be able to take words from your head, put them on paper (or parchment, in this case), and then send them much farther away in both time and space to someone who absolutely cannot hear you say these words, and then put those thoughts in their head.
Which meant that you have this sort of weird liminal thing where "leu" could be spelled "lev", because u and v were interchangeable, and then also this thing where v and f were interchangeable, and both were being sent around to various places and read to others who may, or may not, do a lot of reading as opposed to a little, or may be reading in a different dialect than they speak (because remember, we're talking about mediaeval France, which means we're actually talking about a country with two major language divisions - Langue D'oc and Langue D'oïl - which then inside of them have a reasonable fuckload of languages that are mostly mutually intelligible most of the time), and so on, which means that the noise for u and the noise for f meet in the middle and may both be represented by "v" and while we're at it they may all just be pronouncing the word differently, and as you saw in the whole move from "locus" to "leu" in the first place, that can involve ending up in quite a different place through a totally logical means.
We don't know for absolute certain if this is why the word "leu", ported over to English with the Normans and added to our language, changed its pronunciation and spelling to "lief" or "liev". You will note that along the way both to Middle English and to Middle French, it grew an "i" in before the "e" sound, because words do that.
We do have some records of Old French that are spelled "leuf" or "lef"; we also got our Frenchishness from the Norman Conquest, which is to say the brand of French very specifically spoken by a bunch of Francicized Scandinavians who spoke a very specific one of those Langues D'oïl. So we do know that the idea that this word ended in the sound we might associate with the letter "f" had already took up in a bunch of different places.
The original idea of "lieutenant" is quite literally a "placeholder" - it was someone you left in your place. So if you were your overlord's "lieutenant" you were the person who gave other people orders in his place, the person he delegated to. Much like "captain", when these words were first used they did not designate a specific rank in a highly developed system with rigid relationships, but rather were the names for roles that people occupied in relationship to the enterprise/activity/whatever.
This is why in the books, the Witch King of Angmar is referred to frequently as Sauron's "lieutenant" - Tolkien knew this shit preeeeetty well and liked using words in those contexts.
So in French, they moved along the path of saying "lieu" as the word is said in French today, with no consonant at the end. Their "lieutenant", their "placeholder", maintained that pronunciation. Americans then actively wanted to distance themselves from the British and were at the time buddy-buddy with the French, so they took that pronunciation on.
Meanwhile at some point Middle English - arising from Old English and Norman French - had shifted to the "liev", the one that had a fricative on the end, which was one of the pronunciations attested in the spelling shift to "leuf".
