You misunderstood what SameQ does. SameQ tests for structural equality. It doesn't care about the meaning of the expressions at all. If their full form looks the same, then they're the same. Otherwise not.
While adding the Orderless attribute to UndirectedEdge works in this simple test, I absolutely do not recommend modifying builtin functions like this, especially if you are a beginner. Sooner or later one of these modified functions is going to come back and bite you hard when you least expect it.
If you are certain that such a modification is the best solution, always isolate it using Block or Internal`InheritedBlock, and make sure that it has an effect only on a small piece of simple code.
Internal`InheritedBlock[{UndirectedEdge},
SetAttributes[UndirctedEdge, Orderless];
<<your code here>>
]
For your application, I would bring the lists to a canonical form in the spirit described here:
canonical[edgeList_] := Union[Sort /@ edgeList]
Test if two edge lists are the same using canonical[edgeList1] === canonical[edgeList2].
