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$ has exactly $i+j$ previously-colored adjacent edges going to $B$ and exactly $(p-i) + (p-j) - 1 = 2p - (i+j) - 1$ previously-colored adjacent edges within $A$, so that each edge within $A$ is adjacent to at most $2p-1$ previously-colored edges when it is processed, thus has a color available. Color the edges within $B$ the same way.