W 1981 roku oponował przeciw izolacjonistycznej polityce Hoxhy (pogłębionej po zerwaniu w 1976 współpracy z Chinami). Prawdopodobnie w wyniku tego sprzeciwu został uznany i ogłoszony jugosłowiańskim szpiegiem. 17 grudnia 1981 został znaleziony martwy w sypialni w swoim domu w Tiranie z kulą w głowie. Oficjalnie za przyczynę śmierci uznano samobójstwo w wyniku załamania nerwowego.
Shehu został uznany za „wroga publicznego”. Po jego śmierci ogłoszono go agentem nie tylko jugosłowiańskich służb specjalnych, ale także CIA i KGB. Shehu zniknął z kart oficjalnej historii Albanii.
Istnieją hipotezy, że Shehu został zabity na zlecenie Hoxhy, który obawiał się konkurencji w jego osobie. Kontrowersje wokół śmierci Shehu zainspirowały Ismaila Kadare do napisania powieści Pasardhesi (Następca).
Wdowa po Mehmecie Shehu – Fiqrete oraz jego dwóch synów (Skender i Bashkim) zostali uwięzieni bez jakiegokolwiek powodu. Najstarszy syn popełnił samobójstwo, żona zmarła w obozie w 1988. Pozostali dwaj synowie opuścili więzienie w 1991. Po opuszczeniu więzienia młodszy syn Shehu, Bashkim, rozpoczął poszukiwanie szczątków ojca.