This points out that Legended is typeset instead of being evaluated in the kernel evaluation time. The evidence is in that InputForm[p] still contains two Legendeds and the graphics only one.
This is what you need:
Show[ListPlot[Range[10], PlotLegends -> {"a"}, PlotStyle -> Red], ListPlot[Range[10] + 2, PlotLegends -> {"b"}, PlotStyle -> Blue]] // ToBoxes // MakeExpression // InputForm // ReleaseHold ToBoxes forces Legended to do its business to resolve multiple Legendeds during the evaluation time and MakeExpression reconstructs expressions from boxes so you can further parse.