The complete answer to this question is contained in the Knights
polynomials. By definition, the coefficient of $q^k$ in the $m\times n$
knights polynomial, $K_{m,n}(q)$, is the number
of ways that $k$ non-attacking knights can be placed on an $m\times n$
board. Of course, it's a tautology to say that this solves the problem,
but there is an algorithm to compute them. Using this algorithm, the
first six $m\times n$ knights polynomials (per your request) are
\begin{align}
K_{1,1}(q) &= q+1 \\
K_{2,2}(q) &= q^4+4 q^3+6 q^2+4 q+1 \\
K_{3,3}(q) &= 2 q^5+18 q^4+36 q^3+28 q^2+9 q+1\\
K_{4,4}(q) &= 6 q^8+48 q^7+170 q^6+340 q^5+412 q^4+276 q^3+96 q^2+16 q+1\\
K_{5,5}(q) &= q^{13}+15 q^{12}+158 q^{11}+994 q^{10}+3679 q^9+8526 q^8+12996
q^7+13384 q^6 \\
&+ \; 9386 q^5+4436 q^4+1360 q^3+252 q^2+25 q+1\\
K_{6,6}(q) &= 2 q^{18}+40 q^{17}+393 q^{16}+2560 q^{15}+12488 q^{14}+47684
q^{13}+141969 q^{12} \\
&+ \; 323476 q^{11}+556274 q^{10}+716804 q^9+688946
q^8+491140 q^7+257318 q^6 \\
&+ \; 97580 q^5+26133 q^4+4752 q^3+550 q^2+36 q+1
\end{align}
Note that these polynomials agree with the results that you provide. For example, the coefficient of $q^{15}$ in $K_{6,6}$ is 2560, corresponding to your statement that $M=6,N=15 \Rightarrow \text{ans} =2560$. The coefficients of $q^2$ also agree with this OEIS sequence.
The algorithm to compute these is very similar to the obviously related Kings
problem. Neil Calkin and his REU students provide a very thorough analysis
of that problem in two papers in Congressus Numerantium. Shaina Race has a
publicly accessible presentation of their results here. I published a paper presenting
an implementation of the algorithm in Mathematica V5. The technique for counting
knights is a bit more complicated but uses very similar ideas. Unfortunately,
I've been able to compute the $7\times 7$ knights polynomial but my computer
chokes on $8\times 8$, the size of an actual chess board.
I don't think it is easy to go from (a) to (b) or vice versa (unless the numbers are very small).
Part (b) is much easier. It is solved by stars and bars and has a closed-form solution (in fact, a binomial coefficient).
For part (a), we're talking about integer partitions but with the additional restriction that the number of parts $\le 4$. The wiki article includes the restricted case where the number of parts is exactly $k$, so I suppose you can sum over $k \in [1, 4]$. Anyway, I don't think there is a general solution. Here is a related MSE thread which limits both the number of parts to $\le k$ and the size of each part to $\le d$. So if we set $d=c$ so that each part is unlimited but the number of parts is still limited to $\le k$ then this becomes the OP question.
Best Answer
The first King could be on a corner square($4$ ways), leaving $60$ other squares for the next King.
The first King could be on a edge square($24$ ways), leaving $58$ other squares for the next King.
The first King could be on a central square($36$ ways), leaving $55$ other squares for the next King.
This will double count the configurations, so we have $(4 \times 60 + 24 \times 58 + 36 \times 55)/2 =\color{red}{1806}$.