I would try to group your paths in such a way that if two paths can equal each other they end up in the same group. A "can-equal" test, if you will, that you can apply in a single pass through the edges of each graph. It's much better to have a bunch of little groups to cross-product compare with each other than to have one big group.
To group them, I don't know if you can compute a hashcode, or if the nodes have coordinates that can be compared, or the edges have slopes that can be compared, or what. But I think the first step is to try to limit the number of items you have to compare with other items. If you are looking at a general-case solution that applies to any graph without knowing anything about the items in that graph, you either have to model a way for the implementation of that graph to specify some sort of ordering or partitioning, or I think you are out of luck.
Hmm... That sounds a lot like "Use a Hash Table." But how? I think "similar" paths must mean edges between "equal" nodes for some definition of "similar" and "equals."
Load the nodes of each graph into a hashtable/set (one pass through each graph). Then pick the smaller hashtable, and for each node see if it has a corresponding node in the other hashtable. You don't need to consider any nodes that fail this test or any edges that touch nodes that fail that test. Now you only have edges that are contained in both graphs and maybe the size of that set is the similarity value you are looking for? Or maybe it's the largest sub-graph of edges meeting this criteria which is your score?
I think you could still be in the case were a tiny part of an enormous problem is still too big to be practically solvable. But in some cases, this may narrow down the problem enough to make it solvable.
This is my first time attempting an answer in this forum, so I hope that it is helpful.