Hoddle, who had drawn five and lost one of his first six games in charge, saw his side cruise to victory thanks to early goals from Seol Ki-Hyeon and Carl Cort.
In the process Wolves managed to collect their first clean sheet in 16 games.
Millwall, who had won at Molineux in the league a month ago, were seriously depleted by injury and suspension problems that robbed them of ten key players.
The makeshift side never recovered from the quickfire double from Wolves.
Their dismal day was summed up in the 66th minute when Barry Hayles collected a pass from Curtis Weston and ghosted past the Wolves goalkeeper Matt Murray only to somehow slice his shot wide from five yards.
Wolves effectively had the game wrapped up inside the opening 11 minutes thanks to Seol and Cort.
Impressive South Korean international Seol scored for the second successive game at Molineux when he latched on to a loose ball.
The former Anderlecht marksman pounced after Cort had seen his shot charged down. Seol rifled his left-foot shot past Graham Stack from 20 yards to celebrate his 26th birthday in style.
Cort put the result beyond doubt three minutes later with a close-range header.
Only 60 seconds earlier, Cort had seen his close-range shot deflected over the bar by Matt Lawrence.
But he proved more clinical when Mark Kennedy whipped in a left-wing cross for Cort to head past Stack.
Wolves eased off after opening up their two-goal lead and allowed Millwall to work their way back into the game.
But they never seriously looked capable of forcing a comeback - Jody Morris and Joe Healy both seeing shots charged down before Hayles' amazing miss.
Wolves' margin of victory would have been greater but for Stack, who saved superbly from Kenny Miller nine minutes into the second half.