Gallium-induced structural failure of aluminium
As you state, it forms an amalgam, just as mercury does. @Jon Custer's explanation is correct, and furthermore, the alloy does not form a protective oxide, so the aluminum oxidizes to $\ce{Al2O3}$ and quickly crumbles. This happens even faster with an Hg-Ga alloy!

BTW, gallium should be safe enough, though expensive, but I would not like to work with mercury without a hood, and without careful containment.

Thanks for the question; this encouraged me to view that amazing demo on Vimeo!