Having looked at this again, the answer $4^5$ is correct for distinguishable letters (and boxes, as Steve Powell has said).
If we have something like form letters (all copies identical - we presume the mailboxes are still distinguishable) , then we do get your answers. I counted them this way:
Five identical letters going into four boxes will leave anywhere from zero to three boxes open.
For no open boxes, there is one more letter than boxes, which can go in one of 4 places.
With one open box, that can be one of 4. One letter goes into each of the three occupied boxes, so we only need to consider arrangements of two "excess" letters among those three boxes. Either the two remaining letters go in one of the three boxes ($\left(\begin{array}{cc}3\\1\end{array}\right) =$ 3 ways), or one letter goes into each of two out of the three boxes ( $\left(\begin{array}{cc}3\\2\end{array}\right) =$3 ways). So this case produces $4 \cdot (3 + 3) = $ 24 arrangements.
Two open boxes can occur in $\left(\begin{array}{cc}4\\2\end{array}\right) =$ 6 ways. There are three "excess" letters to distribute among the two occupied boxes: either all go into one ( $\left(\begin{array}{cc}2\\1\end{array}\right) =$ 2 ways) or two go into one and the remaining third excess letter into the other box (also $\left(\begin{array}{cc}2\\1\end{array}\right) =$ 2 ways). This case produces $6 \cdot (2 + 2) =$ 24 arrangements.
Finally, having three open boxes means that one of 4 possible occupied boxes gets all of the letters.
So, all told, there are only 56 arrangements for the identical letters. (I guess I find partioning easier to check, though having done so, I now see what you are describing in your second case. So distinguishability makes a huge difference in answering this question.)
Best Answer
If we can have more than one letter in a given box, then we just count the number of ways to choose one of six boxes, four times in a row:
$$6\times 6\times 6\times 6 = 6^4=1296$$
If each box can hold at most one letter, then we begin, as you said, by counting the number of ways to choose $4$ of $6$ boxes: $\binom64=\frac{6!}{4!2!}=15$, we can multiply this by the number of orders in which $4$ letters can go into the four chosen boxes: $4!=24$. Thus:
$$\binom64\times 4!=15\times 24=360$$
Both of these solutions assume that the four letters are different. If the letters are indistinguishable, then we have a different counting problem.
Suppose the letters are all the same, and a mailbox can hold more than one. Then, we consider the number of ways to arrange $5$ "bars" and $4$ "stars", where the bars represent separations between adjacent boxes, and stars represent letters. For example:
$$\,\,**\,\,|\,\,*\,\,|\,\,\,\,|\,\,\,\,|\,\,*\,\,|\,\,\,\,$$
would represent two letters in the first box, one in the second, and one in the fifth.
This is a total of $9$ symbols, and they can be arranged as many ways as there are to decide which $4$ of the nine should be "stars":
$$\binom94=\frac{9!}{4!5!}=126$$
Finally, if the boxes can hold at most one letter each, but the letters are indistinguishable, then the answer is simply:
$$\binom64=15$$