Another reason for the discrepancy in efficiency is vehicle size and engine power.
The smallest BMW engine you can buy here is a 200+ hp inline 6. In Europe you an buy a inline 4 producing only 120hp (about the same as a corolla) in a BMW 3.
While the smallest typical engine here is about 1.6L (1.4L now for FIAT), in europe 1.2L is "normal" for a ford fiesta, three cylinder engines are common, and in really small cars like the FIAT 500 two cyclinder engines are common.
And then there is the vehicle size. In the US, Camry/Accord/Taurus sized cars are considered normal family cars. If you drive in Canada, you see that shrink by about one class, so the most common cars are Corolla/Civic/Focus (we've got lots of Camrys, but almost no Avalons or similar sized cars). In Europe, you can shrink that again so Yaris/Fit/Fiesta are now the more common cars (even for families).
To put that in perspective, a Mazda 6 (US family car) weighs 3400 pounds (and is pretty light, a Chrysler 300 is more than 4000 pounds). A Mazda 3 (Canadian norm) is 2900 pounds. A Mazda 2 (European) is a svelt 2200 pounds. The Mazda 6 makes between 170 and 250hp depending on engine, and the Mazda 2 makes 100 (and they have 80hp models in Europe).
As was previously stated, this is all driven by a mixture of tight roads and very high gas taxes.