Summary of answer:
Praise be to Allah
Lying is one of the characteristics of the hypocrites, and it is a blameworthy trait which encourages one to commit evil and prevents one from doing good. Al-Bukhaari (6094) and Muslim (2607) narrated that Ibn Mas‘ood (may Allah be pleased with him) said: The Messenger of Allah (blessings and peace of Allah be upon him) said: “I enjoin you to be truthful, for truthfulness leads to righteousness and righteousness leads to Paradise. A man may continue to tell the truth and endeavour to be truthful until he is recorded with Allah as a speaker of truth. And beware of lying, for lying leads to wickedness and wickedness leads to Hell. A man may continue to tell lies and endeavour to tell lies, until he is recorded with Allah as a liar.”
The worst kind of lying is telling lies about Allah and His Messenger, then spreading lies among people in order to cause trouble between them. Habitually telling lies when speaking is one of the characteristics of the hypocrites, as the Prophet (blessings and peace of Allah be upon him) said: “There are four characteristics, whoever has them all is a pure hypocrite, and whoever has one of them has one of the characteristics of hypocrisy, until he gives it up: when he is entrusted with something, he betrays that trust, when he speaks he lies, when he makes a covenant he betrays it, and when he disputes he resorts to obscene speech.”
Narrated by al-Bukhaari (34) and Muslim (58).
What the one who has lied must do – even if he told a single lie – is repent to Allah, may He be exalted. At-Tirmidhi (1973) narrated that ‘Aa’ishah said: No characteristic was more hateful to the Messenger of Allah (blessings and peace of Allah be upon him) than lying. If a man told a lie in the presence of the Prophet (blessings and peace of Allah be upon him), he would continue to feel some unrest in his heart until he knew that the man had repented.
Classed as saheeh by al-Albaani in as-Saheehah (2052).
We could not find any source for the hadith mentioned in the question, after researching the matter. What appears to be the case is that it is falsely attributed to the Messenger of Allah (blessings and peace of Allah be upon him). The scholars stated that one of the signs of a fabricated hadith is that it mentions an exaggerated reward or punishment for a particular deed, and this hadith is like that.
The basic principle is that zina is worse than telling lies, hence sins are mentioned in decreasing order of gravity, after the sins of ascribing partners to Allah (shirk) and murder, in the verse in which Allah, may He be exalted, says (interpretation of the meaning):
“And those who invoke not any other ilaah (god) along with Allah, nor kill such life as Allah has forbidden, except for just cause, nor commit illegal sexual intercourse and whoever does this shall receive the punishment”
With regard to zina, there is the prescription of punishment in this world (the hadd punishment), and the warning of punishment in the Hereafter, such as is not mentioned in the case of lying. However, some kinds of lying are worse than zina and other major sins, such as telling lies against Allah and His Messenger. Allah, may He be exalted, says (interpretation of the meaning):
“Say: ‘Verily, those who invent lies against Allah will never be successful’”
The Prophet (blessings and peace of Allah be upon him) said, in the mutawaatir hadith: “Whoever tells a lie against me deliberately, let him take his place in Hell.”
With regard to saying that lying as a whole is worse than zina, this is incorrect, let alone saying that it is worse than committing zina seventy times (“seventy fornications”), the least of which is fornication with one’s mother. This is among the silliest of notions and most obvious of lies, and is impossible!
With regard to the report narrated by Ibn ‘Asaakir in his Tareekh (27/241) from ‘Abdullah ibn Jaraad – according to which he asked the Prophet (blessings and peace of Allah be upon him: O Prophet of Allah, can a believer commit zina? And he said: “That may happen.”
He said: Can a believer steal? He said: “That may happen.”
He said: Can a believer tell lies? He said” No; rather lies are fabricated by those who do not believe”–
this is a false hadith. Its isnaad includes Ya‘la ibn al-Ashdaq. Ibn Hibbaan said: They fabricated hadiths for him and he narrated them without realising. Abu Zar‘ah said: He is nothing; he does not tell the truth.
Mizaan al-I‘tidaal (4/475).
It was mentioned by al-Albaani in ad-Da‘eefah (5521), where he said: It is da‘eef (weak).
Something similar may be said about the hadith of Safwaan ibn Sulaym: It was said to the Messenger of Allah (blessings and peace of Allah be upon him): Can a believer be a coward?
He said: “Yes.”
It was said to him: Can a believer be a miser?
He said: “Yes.”
It was said to him: Can a believer be a liar?
He said: “No.”
Narrated by Maalik (3630). It is mursal, and was classed as da‘eef by al-Albaani in Da‘eef at-Targheeb wa’t-Tarheeb (1752).