Before we get to the meat of the question, note that this is a feature of most parliamentary systems of government. While most of the countries in Europe are indeed examples of this, plenty of countries elsewhere in the world are as well - such as Canada, Israel, India, Japan and Australia (more here and here).
On the other hand, European Parliamentary leaders like Germany's Angela Merkel or the UK's Theresa May appear to be more entrenched in their party's leadership,
As Relaxed mentions, this is a little bit backwards if we consider how a person becomes Prime Minister. As a minimum, they must have the confidence of the lower (or only) house of parliament, meaning that they should be able win most parliamentary votes.
This means having a majority of MPs who will follow your lead, and political parties are the practical method of achieving this. If one party has a majority, then the leader of that party is most likely to be able to win most votes in parliament, and therefore they are the ideal choice for Prime Minister.
If no party has a majority on its own, then parties may join together to form a coalition government, and decide between themselves who will become Prime Minister.
meaning that they may remain party leaders even if they lose an election.
Yes, because party leader and Prime Minister are separate roles. There are many party leaders, but only one PM at a time; and there is typically no requirement for the PM to be a party leader, though this is hard to achieve in practise.
In the UK, when a governing party loses at a general election, it has become common for the former PM to resign as leader, and sometimes as an MP as well - though again, there is no requirement to do so.
On a technical note, I wouldn't describe the post of Prime Minister (or equivalent, e.g. Chancellor) as a parliamentary leader, except in the sense that party leaders make frequent appearances in parliament. The PM is the head of government, and while they normally obtain that position due to parliamentary arithmetic, it's their party and their government that they lead.