I think it mostly has something to do with the directness of democracy, not with a difference in opinion or mentality.
Democracy in the US is very local and direct, politicians can actually be punished by the voters for not being tough on crime. That’s not so easy in (for example) Germany. You vote predominantly for parties – the whole package – not politicians. Something as comparatively unimportant as criminal law is going to get swamped by all the other issues, hardly anybody will focus on the particular weak spots of one lowly member of parliament. That would be a waste of effort.
Moreover all decisions about the criminal law are made on the federal level, in commissions full of experts (a lot of academics: criminologists, psychologists …). There is no reason for politicians in those commissions not to follow their recommendations. Voters will hardly ever notice what they decide, it is going to get lost under all the other issues.
You can actually be successful as a German politician who has a image for being tough on crime on the very local level (in, say, a city state), but on that level you can do no more than strictly enforce the rules that already exist. That will hardly change incarceration rates, though.
You don’t need a culture shift, you need a different political system :)