SQL Server "empty table" is slow after deleting all (12 million) records?
You've already been told about why TRUNCATE would be so much faster/better/sexier than DELETE, but there's still a question left to address: 

Why is SELECT slower after DELETE completed?

That is because DELETE has only ghosted the rows. The table is just as big as when it had 12M rows, even though it has none. To count the rows (0), it takes just as much time it took to count 12M rows. In time the ghost cleanup process will garbage collect these ghosted records and deallocate pages that contained only ghosts, and your SELECTs will speed up. But right now if you check Skipped Ghosted Records/sec in perfmon is probably skyrocketing during SELECT COUNT(*). You could also speed up things by rebuilding the table: ALTER TABLE ... REBUILD.

TRUNCATE would had also taken care of this problem, as it leaves no ghosts behind.

See also Inside the Storage Engine: Ghost cleanup in depth.