Ah, so maybe they did have wings...

[Gwaihir the Windlord]

Deep in forgotten places that cry (Morgoth's as he was attacked by Ungoliant) was heard. Far beneath the ruined halls of Angband, in vaults to which the Valar in the haste of their assault had not descended, Balrogs lurked still, awaiting ever the return of their Lord; and now swiftly they arose, and passing over Hithlum they came to Lammoth as a tempest of fire.

The distance between Angband, which doesn't even appear on the Silm's Beleriand map, and LLammoth where Morgoth and Ungoliant were was quite a substantial one. Unless the Balrog's running speed was truly incredible, they surely would not have made the journey in time to save their Lord from the spider's dark belly unless they flew.

That they 'passed over Hithlum' supports this. However, it may also be that they simply climbed over or found a pass through them, and that Morgoth was able to elude and defend against Ungoliant for the time it took them to get there. All the same, it sounds tantalisingly like they did fly there.