It's less efficient because it's expecting more data. I'd hazard a guess that, due to the high estimated row count, that the query immediately ended up using a worktable on tempdb, where as with the lower row count it was about to do the work in memory. Writing and reading from tempdb is far slower than doing processes in memory (unless you have some crazy fast storage device for your tempdb).