The "extra mile" probably comes from Matthew 5:41 "If someone forces you to go one mile, go with him two miles." (or "And whosoever shall compel thee to go a mile, go with him twain.") You used the phrase perfectly in your comment -- it's about going above and beyond what was expected.

The mileage comment was more from the auto manufacturers / EPA who tested cars. A car will have been tested on specific conditions and found to achieve a certain Miles per Gallon. However - accelerate/brake hard, drive more in the city or other different conditions and you would get a completely different result. Hence the standard disclaimer of "your mileage may vary..." That made it's way into the lingo as a standard phrase meaning "this is pretty subjective - it might be the same for you, it might not"

So aside from the word "mileage" being derived from the base word "mile", there isn't much overlap between the two phrases.

(Oh - and a related note for my American friends - as much as I hate imperial units - I will give you credit that mileage is a nice word. litres/100km is still a better unit than MPG, but mileage is a better term than fuel efficiency (or kilometreage).)

Taking this WAY off topic ...

"Your mileage may vary" was a disclaimer on car advertisements (because you never achieve the advertised miles-per-gallon).

"Go the extra mile" is biblical: Matthew 5:41

Nah, I think the expression came from car commercials that advertised "X miles per gallon (but your milage may vary)" to avoid getting sued for false advertising or some such.

It’s not exactly an unresearched problem. Here’s from 1983:

http://www.tug.org/docs/liang/

Here’s a javascript version:

http://code.google.com/p/hyphenator/