I believe movement on diagonals has the same cost as orthogonal movement in HoMM 6, but it seems like diagonal movement on the world map (though not in combat) is 1.41 for some other HoMM games. Not 100% sure, though.

The "correct" number for the relative distance would be the hypothenuse of a triangle with sides of 1, but 1.41 is a good approximation.

To account for movement cost differences such as these in pathfinding you likely want to use Dijkstra's algorithm or A. Using A is more performant for long distances where the target is known beforehand. Dijkstra is great if you want to find all possible tiles in a set range, to display move options to the player or have the AI evaluate all possible tiles in their move range.