Efficient computation of Kronecker product
You cannot fill a matrix with $n_1 n_2 m_1 m_2$ entries in time faster than $\Theta(n_1 n_2 m_1 m_2)$. Some considerations:


There may be a way to reduce the number of multiplications (FFT?) by using extra additions, but it won't improve the asymptotic complexity;
This is easy to parallelize;
You can do this on-the-fly, i.e. store the matrix M as "Kronecker product of A and B" and perform the multiplication only after a request for an element M[p,q].
Conceptually you can forget about the rectangular shape of a matrix and think about the situation where you have two vectors $\left[x_1,...,x_k\right], \left[y_1,...,y_m\right]$ and want to compute $k \cdot m$ products $x_i y_j$ for each $i,j$.