Sarkozy suspended French military training and joint combat operations and dispatched Defence Minister Gerard Longuet to probe Friday's attack in which at least 15 French soldiers were wounded, eight seriously.
"The French army stands alongside its allies but we cannot accept that a single one of our soldiers be wounded or killed by our allies, it's unacceptable," Sarkozy said.
"If security conditions are not clearly established, then the question of an early return of the French army will be asked," he said.
A security source said the shooting happened as "the French were just finishing their sports session" at the Gwam base.
"The soldiers were not protected. They could not defend themselves. He fired at the group. Then they neutralised him," the source said.
Longuet described the attack as "murder".
"They were not armed, they were literally murdered by an Afghan soldier. We don't yet know if it was a Taliban who infiltrated or if it was someone who decided to act for reasons as yet unknown," Longuet said.
Foreign Minister Alain Juppe said France would await a report from Longuet and military chief of staff Admiral Edouard Guillaud on their return from Afghanistan before taking any decision on an early pull-out.
"Their main task will be to establish the circumstances and responsibilities of this tragedy and then report to the French government what measures the Afghan authorities promise to undertake to sort out Afghan army recruitment and ensure the French contingent's security," Juppe said.
"Based on this report, the president and the government will decide whether the security conditions are credible.
"If this is not the case, we will draw the conclusions... including the acceleration of a complete withdrawal of our contingent set for the end of 2013," Juppe said.
France has about 3,600 soldiers serving in the country, mainly in the provinces of Kabul and Kapisa, the scene of Friday's shooting.
Their deployment is deeply unpopular in France, and Sarkozy is facing a tough reelection battle in less than three months.
French troops have fanned out around their base in the eastern province and are not allowing any Afghan soldiers to approach, a security source told AFP.
The French force currently in Afghanistan will be reduced to 3,000 by late 2012, with 200 due to leave in March. NATO is due to hand security over to Afghan forces before withdrawing all its combat troops by the end of 2014.
Training Afghan forces and accompanying them into battle against rebels is the core of the French mission within the NATO-led coalition in Afghanistan, the force having already scaled down its own operations.
Afghan President Hamid Karzai sent his condolences to the French people over the deaths, saying relations between the two countries had "always been based on honesty, which makes Afghans happy."
"The president is saddened at the incident and expresses his deep sympathy and condolences to the president and people of France and the victims' families," his office said in a statement.
NATO chief Anders Fogh Rasmussen also expressed his condolences, but insisted the attack was isolated.
"This is a sad day for our troops in Afghanistan and the French people," Rasmussen told reporters during a visit to NATO ally Latvia.
"I would like to express my condolences for the four French soldiers who were killed today and my sympathy to those who were wounded," he said, warning against seeing a new trend of attacks from renegade Afghan troops.
"Such tragic incidents are terrible and grab headlines but they are isolated," he said, noting that 130,000 NATO-led international forces are still serving alongside more than 300,000 Afghans.
The latest deaths brought to 82 the number of French soldiers killed in Afghanistan since French forces deployed there at the end of 2001.
Suicide attacks, roadside bombs and insurgent attacks had a heavy toll on French troops in 2011. A total of 26 were killed, the most in a single year during the 10-year war.
The shooting was the latest in a string of incidents of Afghan soldiers turning their weapons on members of the foreign force fighting an insurgency by hardline Taliban Islamists.
Last month, two soldiers of the French Foreign Legion serving in Afghanistan were shot dead by a man wearing an Afghan army uniform during a mission in Kapisa, site of the main French base in Afghanistan.
The Taliban claimed responsibility for that attack.
In April last year eight US soldiers were killed in a shooting at a military airport in Kabul, but a Pentagon report this month said the killings were the actions of a disturbed Afghan military officer who acted alone.
While some attacks have been claimed by the Taliban, others have been put down to arguments or personal animosity between soldiers from the two forces serving together.