Relevant quote from The Two Towers; Chapter 5, The White Rider:
'Then tell us what you will, and time allows!' said Gimli. 'Come,
Gandalf, tell us how you fared with the Balrog!'
'Name him not!' said
Gandalf, and for a moment it seemed that a cloud of pain passed over
his face, and he sat silent, looking old as death. 'Long time I fell,'
he said at last, slowly, as if thinking back with difficulty. 'Long I
fell, and he fell with me. His fire was about me. I was burned. Then
we plunged into the deep water and all was dark. Cold it was as the
tide of death: almost it froze my heart.'
'Deep is the abyss that is
spanned by Durin's Bridge, and none has measured it,' said Gimli.
it has a bottom, beyond light and knowledge,' said Gandalf. 'Thither I
came at last, to the uttermost foundations of stone. He was with me
still. His fire was quenched, but now he was a thing of slime,
stronger than a strangling snake.
'We fought far under the living
earth, where time is not counted. Ever he clutched me, and ever I
hewed him, till at last he fled into dark tunnels. They were not made
by Durin's folk, Gimli son of Glóin. Far, far below the deepest
delving of the Dwarves, the world is gnawed by nameless things. Even
Sauron knows them not. They are older than he. Now I have walked
there, but I will bring no report to darken the light of day. In that
despair my enemy was my only hope, and I pursued him, clutching at his
heel. Thus he brought me back at last to the secret ways of Khazaddûm:
too well he knew them all. Ever up now we went, until we came to the
'Long has that been lost,' said Gimli. 'Many have said
that it was never made save in legend, but others say that it was
In Gandalf's battle with the beast, they were indeed submereged in water. That did not kill the Balrog, or even weaken him really. It did put out his flame, and reduced him to a muddy serpentlike creature.