Deletes are very, very expensive to perform. And it gets worse the more rows that are deleted. The reasons are logging, locks, referential checking, etc. The best solution is to break up deleting that many rows into smaller units of work instead of one big one. See if you can delete them in 10,000 row chunks or smaller and COMMITing after each chunk.
HTH
Andy