The Home Office is looking into reports that hundreds of foreign offenders have been freed from secure hospitals with no consideration given to deportation.
John Reid has admitted to another Home Office mistake
The Sun says police are seeking up to 500 former mental patients, including murderers, rapists and paedophiles.
The Home Office said Home Secretary John Reid had ordered officials to identify exactly how many foreigners had passed through UK secure hospitals.
Police are still seeking some of more than 1,019 foreigners freed from jail.
Updating MPs on the foreign prisoner crisis earlier this week, Mr Reid admitted no information on the nationality of offenders in mental institutions had been collected and none had been considered for deportation or even referred to the Immigration and Nationality Directorate.
The three secure hospitals in England where mentally-ill prisoners are held are at Broadmoor in Berkshire, Rampton in Nottinghamshire and Ashworth on Merseyside.
A Home Office spokesman said if any of the "mentally disordered offenders whose restrictions have ended" could now be "identified as foreign nationals" they would "be considered for deportation as soon as possible".
No-one is discharged from a secure hospital without their cases being considered by a mental health tribunal.
But shadow home secretary David Davis said: "Given the fact that these criminals have been deemed mentally ill, presumably it is even harder to predict whether they continue to be a risk to the public.
"This is a matter of serious risk to the public.
"John Reid should have told us all and notified every chief of police in the country as soon as it became clear an error had been made.
"This is a desperately serious problem for a Home Office already in crisis."
Marjorie Wallace, chief executive of mental health charity Sane, said foreign offenders were "at especially high risk" of suffering "returning mental illness or disorder" because they were "dispossessed from their own countries" and less likely to have "close family or community support".
"Such patients should be monitored closely for their own support and protection and that of others... to ensure that after release they receive any treatment they may need to prevent relapse."
Former minister Barbara Roche said the Home Office should no longer compile figures.
Ms Roche, a former Home Office minister, told BBC Radio 4's Today programme: "We ought to have independent statistics on immigration and asylum.
"We ought to have something like the Electoral Commission that can give advice to government and would give some independence to the whole range of statistics that we see coming out."
She said the Home Office had been "caught by surprise" because it focused on criminal justice policy rather than issues of immigration and asylum.
Ms Roche added that the system was being "increasingly overwhelmed" and said both the government and officials had to sort the problems out.
While there are good officials, other ones did not know what being in charge of a modern department was all about, she added.