You need to delete in batches. I've done that dozens of times without issues on tables with several millions records. But regardless, you table will be fragmented once you're done, no way to avoid that.

Here's an example:

--DELETING LARGE AMOUNTS OF DATA

DECLARE @Done BIT

SET @Done = 0

WHILE @Done = 0

BEGIN

DELETE TOP (20000) -- reduce if log still growing

FROM SomeTable WHERE SomeColumn = SomeValue

IF @@ROWCOUNT = 0

SET @Done = 1

CHECKPOINT -- marks log space reusable in simple recovery

END

Also, keep an eye on your Tlog, it may growth while you do this.