There is a precedent in a UK-style electoral system: In the 1989 provincial election in Alberta, Canada, the Progressive Conservative party won a majority while its leader, Don Getty, lost his own seat.
The matter was resolved by persuading a Progressive Conservative member in a safe seat to resign, allowing Getty to run in the resulting by-election and win a place in the provincial assembly.
In the UK, the Prime Minister does not need a seat in Parliament, although by custom he or she is expected to have one:
In theory a Government minister does not have to be a member of either House of Parliament.
In practice, however, convention is that ministers must be members of either the House of Commons or House of Lords in order to be accountable to Parliament.
So in this situation, the party leader would have three options:
Arrange to be appointed to the House of Lords;
Return to the House of Commons via a by-election, as in the Alberta case.
In theory, any of these would comply with the letter of the law and allow the party leader to serve as Prime Minister. In practice, there would be very strong public demand for the Prime Minister to be a member of the House of Commons, so option (3) would probably be chosen.
A by-election could be arranged within a few weeks. The retiring MP could be rewarded with a seat in the House of Lords and/or a desirable government job. The Prime Minister would face some opposition in the new constituency; but if the party was sufficiently strong there, he or she would probably still win the by-election comfortably.