By custom.
Paper is just paper. Law is just paper that people agree is important.
Custom is stronger than law.
Canada has a similar parliamentary system. For the longest time, it was not fully sovereign, as it was a dominion of the UK. Over time it became more sovereign, as the custom of defering to the UK fell away. In WW1 it went to war automatically when the UK did; in WW2, it went to war independently.
Eventually, it wrote itself a constitution. It went through extraordinary processes in the writing of said constitution, including consulting the bodies that make up the nation. Then it passed a parliamentary law saying that this was Canada's constitution.
This constitution (and related legal work) set up a bill of rights and established how itself was to be changed.
Now, had another party decided that the constitution should be discarded immediately, ran on that, won the next majority, then passed a law throwing it out, odds are parliamentary sovereignty would have won the day.
It has now been 35 years since Canada adopted its constitution. Long fights have occurred over amending it, but nobody has seriously stated "just pass a law and dismantle it" in a long time. By custom (and its text), parliament can only change it by consulting with the provinces and having a referendum on the subject with certain strict criteria to pass the amendment.
If parliament where to pass a law scrapping it, the Canadian supreme court would probably at this point say "no" (you can never be certain). And then parliament could scrap said supreme court, because rulings are just paper and words. If they got away with it, they'd get away with it.
Given sufficient time and respect, the text of the constitution written could become strong enough that the institutions of the nation -- the courts, the people, the houses -- would react strongly to attempts to declare it null and void. It would remain a piece of paper; it would be the willingness of people to stand up and say "no, you aren't allowed to do that" that would prevent it from being thrown away.
When the point is reached that the parliament throwing away the constitution would be viewed as horrible and get as much obedience as the parliament saying "everyone who is left handed must be killed, not doing so is a crime", then the constitution trumps parliamentary sovereignty.
Well, before that too.