Saudi state television broadcast pictures on Saturday it said were of al-Muqrin and three other dissidents.
All four had been involved in recent attacks on foreigners in the kingdom, it said. The television also said 12 people suspected of involvement in the violence had been arrested and were being investigated.
However, a statement posted on a website which regularly published purported al-Qaida statements said that al-Muqrin is not dead.
"Following the lies ... about the death of Abd al-Aziz al-Muqrin, we affirm that such allegations, spread by the tyrants in Saudi Arabia, are intended to undermine the morale of the mujahadin on the Arabian peninsula," said the statement.
The authenticity of the statement could not be confirmed.
But al-Muqrin's death has been verified based on the pictures, forensic tests and family identification, Saudi political analyst Zuhair Harthy told Aljazeera.
He dismissed the website statement, saying they were trying to create a "media tempest" to shake what he said is the triumph of the Saudi authorities.
Saudi security official said a witness noted the licence-plate number of a car from which Paul Marshall Johnson's body was dumped just outside Riyadh on Friday and informed police.
Police stopped the car at a petrol station in central Riyadh and a shootout ensued in which al-Muqrin, Rakan Muhsan Muhammad al-Saykhan - the second most-wanted Saudi fugitive - and three other fighters were killed, said Saudi officials and Washington.
Saudi officials are hard pressed
to halt the wave of attacks
The killing of al-Muqrin, 31, would be a coup for the Saudi government, which has been under intense pressure to halt a wave of attacks against Westerners in the kingdom.
"The killing of al-Muqrin would raise our morale after the gruesome murder of the US victim Johnson," Saudi journalist Khalid Salih al-Shashri told Aljazeera.
"Johnson's beheading has gripped the Saudi public in a sense of grief," he added.
Late on Friday Johnson's captors killed him after a 72-hour deadline for the Saudi government to release al-Qaida prisoners passed. The Saudi government had rejected the captors' demands.
Political analyst Munthar Sulaiman said al-Muqrin's death did not indicate a success for Washington's "war on terror" as the group he headed was well organised and the death of its leader would not harm it.
The US is not keen to withdraw from Saudi Arabia or give up its interests in the Middle East including Riyadh, he told Aljazeera.
"This act is to heal the hearts of believers in Palestine, Afghanistan, Iraq and the Arabian Peninsula"
statement issued in the name of Falluja Brigade of al-Qaida in
the Arabian Peninsula
Washington may reduce the number of US citizens in the kingdom, especially the secondary staff in the embassy in Riyadh, in addition to advising them not to leave their residence, said Sulaiman.
Suleiman said Washington had reiterated its commitment to its "war on terror" and its cooperation with the Saudi Arabian authorities.
Series of attacks
Johnson, 49, was an employee of defence contractor Lockheed Martin, which manufactures US helicopter gunships. He was an engineer who repaired Apache helicopters and worked in the kingdom for over a decade.
His severed head was shown on a website on Friday. The photographs and a statement, in the name of Falluja Brigade of al-Qaida in the Arabian Peninsula, appeared after Johnson's wife went on Arab television and tearfully pleaded for his release.
A purported al-Qaida tape claimed
another killing of a US national
"Let him [Johnson] taste something of what Muslims have long tasted from Apache helicopter fire and missiles," said a statement which accompanied the pictures.
"This act is to heal the hearts of believers in Palestine, Afghanistan, Iraq and the Arabian Peninsula," it said.
Johnson was the latest victim of an escalating campaign of violence against Westerners that aims to drive foreign workers from the kingdom and undermine the ruling royal family.
Body not found
Saudi officials on Saturday said they still had not recovered his body despite earlier media reports.
"The body has not yet been recovered,” said Saudi foreign policy adviser Adil al-Jubair. There was confusion on Friday about this issue.
"The determination that Mr Johnson was murdered was made on the basis of technical analysis of the tape (of the beheading) by both US and Saudi experts. We do not yet know at what time Mr Johnson was murdered," he said.
"We are searching for the body," which is thought to be in the northern outskirts of Riyadh, al-Jubair added.
He was seized the same day that dissidents shot and killed American Kenneth Scroggs in his garage in Riyadh.
Scroggs worked for Advanced Electronics Co., a Saudi firm whose website lists Lockheed Martin among its customers. The office number on Johnson's business card was for Advanced Electronics.
The same week as Scroggs' death, dissidents shot and killed another American, Robert Jacobs, and Irish citizen Simon Cumbers in Riyadh.