A British volunteer carries a child ashore on the Greek island of Lesbos. Photo: DPA
Some migrants entering Europe without the right to asylum should be "locked up if necessary", Frontex director Fabrice Leggeri told the tabloid.
"Anyone who has entered illegally and has no right to asylum must quickly be sent back to his homeland," Leggeri added.
Under EU law, it's possible to keep irregular migrants in detention for up to 18 months to organize their return home.
Leggeri said that the figure of 800,000 was only provisional, as many more people were on their way towards the EU from crisis regions in Africa and the Middle East, with the high point of refugee arrivals "not yet reached".
"EU states must prepare for the fact that we still have a very difficult situation ahead of us in the coming months," added Leggeri.
Last month, Frontex said that 710,000 migrants had entered the EU in the first nine months of the year but cautioned that many people had been counted twice.
The agency said on October 13 that "irregular border crossings may be attempted by the same person several times".
"This means that a large number of the people who were counted when they arrived in Greece were again counted when entering the EU for the second time through Hungary or Croatia," explained the agency.
According to the most recent figures from the UN refugee agency, more than 744,000 people have made the perilous journey across the Mediterranean this year, the majority to Greece.
In October alone, more than 218,000 people crossed the sea, the UN reported on Monday - a record for 2015 and more than arrived in all of 2014.
On Wednesday, the first set of 30 migrants was due to leave Athens for Luxembourg under an EU plan to redistribute people throughout the 28-member bloc in order to ease pressure on countries like Greece and Italy.
The bloc hopes to transfer some 160,000 people under the plan.
SEE ALSO: Merkel announces hard-fought refugee deal