Short answer: Vacuum your table. (Newer versions are usually set to autovacuum.)
Long answer: This is a well documented problem with the MVCC approach that Postgres uses. It creates 10 million rows and when you delete them it marks them as deleted but any processes that were started before the delete statement would still be able to view them all. It doesn't physically remove the dead rows until you run vacuum. So running select count will actually make it read thru 10,000,010 rows to find the 10 live ones.
When making major changes to the numbers of records, always include a vacuum step after the record counts change. as rskl/artacus72 have mentioned, this is a well-known side effect of mvcc.
"Lisa, in this house, we obey the laws of thermodynamics!" - Homer Simpson
"I have my standards. They may be low, but I have them!" - Bette Middler
"It's a book about a Spanish guy named Manual. You should read it." - Dilbert