Ideally it would be something that involved over 60% approval and approval by other government bodies as well. Judicial and/or legislative. There are many was to structure it, but the point is that major structural changes to a government should be difficult and slow.
Democracy is as much an acknowledgment of the importance of dissensus as it is of consensus. Simple majority rule is de facto mob rule when it's unchecked.
In order to hold a referendum, most countries require you to have legislative assent - i.e., David Cameron couldn't just announce there was going to be an EU referendum, he had to introduce a bill for a referendum into parliament, which was then passed by parliament. This is also the case in Turkey. The judiciary's 'assent' is not required because the point of the judiciary is that they are not law-makers, the only judicial assent you need is that the way in which the referendum is carried out is not in breach of existing laws.
But even if we ignore that and focus on your main point: if you think that constitutional changes should always require supermajorities, if I go to the Irish gay marriage referendum thread, I'll find you complaining about how there wasn't a clear enough mandate, will I? Because I'm pretty sure I won't find you doing that.
Let's be clear: this is a terrible result, and it's an undemocratic result. But that's because Erdogan effectively 'rigged' the election by neutering the opposition. Suggesting an undemocratic measure as a response by making referendums favour the past over the present, especially when the past is normally, if not always, more sexist, racist, and classist, is not the right thing to do.