 Solution

Distribute every term of one input across every term of the other, using the same private accumulator:

mulPoly(x,y):
    r = NIL
    p = x
    while p != NIL:
        q = y
        while q != NIL:
            accumulate(r,p.coeff*q.coeff,p.power+q.power)
            q = q.next
        p = p.next
    return r

The inner-loop invariant says that the current result contains all products from earlier nodes of x, plus the current x node multiplied by the processed prefix of y. The outer invariant is the corresponding statement for completed rows of products. The distributive property then proves correctness. Powers add, equal powers combine, zero products and cancellations disappear. Both input lists are only read, and an empty input gives the zero polynomial.

There are $mn$ coefficient products. If at most $u$ result nodes are present at a time, the simple unsorted accumulator costs $O(mn(1+u))$, with $u\le mn$; it is correct without claiming a linear-time multiplication.