McCullum hit 188-ball 202 while Williamson made 192 as New Zealand closed the third day at 637-8 with a world record of 19 sixes to pulversie a hapless Pakistan.
That gave New Zealand a mammoth lead of 286 runs over Pakistan's first innings total of 351, setting them up strongly for a series-levelling win.
Pakistan lead the three-match series 1-0 after winning the first Test in Abu Dhabi by 248 runs and drawing the second in Dubai.
This also becomes the highest total by New Zealand against Pakistan, beating the 563 they made at Hobart in 2003.
More From This Section
Ross Taylor, Corey Anderson and Tim Southee all made 50 each to enjoy a dominating day for their team.
In the morning McCullum became one of only four batsmen to score three double-hundreds in a year.
The New Zealand skipper also created a new second-wicket record for New Zealand in all Test cricket of 297 with Williamson.
- Over the roof -
McCullum jumped out of his crease to hit Shah over the stadium roof at long-on for his 11th six to complete his double-hundred off just 186 deliveries.
This is his third double-hundred this year, following his two against India at home in February, making him the fourth batsmen to score three or more double-hundreds in a year.
Michael Clarke (four scores of over 200 in 2012) Ricky Ponting (three in 2003) and Don Bradman (three in 1930) -- all from Australia -- are the only other players to have achieved the feat.