Running time - Linked Lists Polynomial
The running time of the InsertTerm subroutine is $\Theta(n)$ where $n$ is the number of terms in the polynomial, and this is the worst-case complexity as well as the average-case complexity absent any information about the monomial being inserted.

The outer loop of PolynomialAdd runs MaxDegree(Poly1.head, Poly2.head) times. Inside each iteration, the inner loops search for a node with the right degrees in each polynomial. For terms of degrees that are absent from the monomial, or present near the end of the monomial, the running time of the inner loop is $\Theta(n)$ where $n$ is the number of terms in the respective monomial. The running time of InsertTerm has been discussed above; here all I need to know is that its $\Theta(n)$. Hence the running time of PolynomialAdd is $\Theta(\max(x,y) \cdot (x + y))$ where $x$ and $y$ are the number of terms in the polynomials Poly1 and Poly2 respectively.

The number of calls to InsertTerm in PolynomialMul is clearly $xy$, since the outer loop always runs $x$ times and the inner loop always runs $y$ times. I assume that Node1.Deg + Node1.Deg is a typo and you really meant Node1.Deg + Node2.Deg. I won't give a full proof here, but intuitively speaking, this is going back and forth inside the result list, and so on average the time spent in insertTerm is about half the length of the list: $\Theta(x+y)$. Therefore the running time of PolynomialMul is $\Theta(x\,y\,(x+y))$.

It is possible to implement polynomial addition and multiplication with faster running times, but you'll need to improve your code. The core idea is that you waste a lot of time in InsertTerm, inserting at random positions in the result list. Instead, arrange to construct the result list in order: first the lowest-degree term at the end of the list, then the previous term, etc. (Alternatively, if you find it easier, construct the list in the other order, starting with the highest-degree term and maintaining a pointer to the next pointer in the last node). Furthermore, do not traverse the arguments again on each iteration through the loop: in addition, iterate over the two arguments simultaneously; in multiplication, where you need to combine terms of different degrees, remember where you stopped so you can start again from the same point.