Greedy coloring works here, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i$ neighbors in $B$ and vice versa.
First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available.
Then color the edges $a_ia_j$ within $A$, ordering the edges so that $a_i + a_j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbors within $A$. OOPS THIS IS NOT QUITE GOOD ENOUGH, WE ARE OFF BY ONE