Why do we believe that the super massive black holes at the centers of two merging galaxies would themselves merge?

The SMBHs reside in the bottom of the galactic potentials, which are dominated by the galaxies' dark matter halos. But although dark matter dominates gravity, collisions between gas and dust particles in the interstellar medium causes enough friction that the baryonic component of the galaxies is decelerated. This will cause the other components of the galaxies to decelerate as well, through gravitational attraction.

Moreover, despite dark matter (and, in practice, stars and black holes since they're so small) being collisionless, there are several ways of "relaxing", i.e. to evolve towards an equilibrium. In the context of galaxy merging, the most important mechanism (I think) is "violent relaxation", where the rapid change of the gravitational potential causes particles to relax, e.g. more massive particles tend to transfer more energy to their lighter neighbors and so become more tightly bound, sinking towards the center of the gravitational potential.

Although SMBHs are…, well, supermassive, the potential will (usually) be dominated by dark matter, gas, and stars, so the new gravitational potential will also cause the SMBHs to seek towards the bottom in the same fashion, and eventually merge.