How do map providers like Google calculate the distance between two coordinates and find turn by turn directions?
Roads maps are well defined and you can access them online. For example you can visit OpenStreetMap to download road network of a given region. 

Such a road network definition contains nodes (junctions) with lat/lon coordinates and edges between nodes (roads). An edge is defined by a connection of two nodes. Edges can represent one-way roads: you need to define double ways as two edges going in both ways. Haversine formula gives you the straight distance between two nodes: the length of the edge. 

This definition of a road network gives you a graph (in the mathematical point of view) and is largely covered by the literature. You can search the graph and compute many of its parameters.

From a road network definition you can run shortest path algorithm to find the closest way between two nodes. From a given coordinate you can either pick the closest node or get the closest edge (and compute distance to the edge and the coordinates of the perpendicular projection point). 

Algorithms like A* and Dijkstra are not so time consuming and you can find shortest path efficiently.