Basic Algorithm
Maintain two sets of the nodes you can reach from the start and end node. In alternating fashion, go three steps from both sides. Each time replacing your set with nodes you can reach through one more step. After each step you check the two sets for common nodes.
Optimizations
Make sure you can iterate the sets as sorted so that you can search for common nodes in a single sweep: an O(n+m) operation. Lists will be up to a million nodes each.
To extend a set with one step, you have query all connections of the nodes in the original set and merge them into a new sorted set. Merging 2 sorted lists can again be done in a single sweep. So you also want to make sure that you can query the connections of a node as sorted. (This could be preprocessed).
In the last two steps each new set is the result of merging up to 10000 of these query results. It is best to do this merge adaptive (merging equally sized chunks). In that way, the sorted set data structure can be a simple linked list.
That way the whole algorithm becomes O(6*n + 6*n*log n) where n is max. 1,000,000.
You should be able to adapt Dijkstra's algorithm.
Just add two points A & B to your graph, which are connected to one of the subgraphs each. Then calculate the shortest path between the two points A & B.
The shortest path between the two subgraphs should be the path that you get after removing A & B from the result.
Best Answer
Follow your Eulerian cycle. Whenever you arrive at a vertex you've been at before, the part between the two visits is a simple cycle. Chop that off and store it in the list of simple cycles, mark all vertices used in that, except the one you are at now, as unvisited. Continue until all edges have been used.
To find a Eulerian cycle, Hierholzer's method is efficient.