(1) When $n \ge 2$, if $a_1 < a_2 < \overline{a_1a_2\cdots a_n}$ is classified as A class. The number of $\overline{a_1a_2\cdots a_n}$ is denoted by $g(n)$. If $a_1 > a_2$, then $\overline{a_1a_2\cdots a_n}$ is classified as B class. By symmetry, the number of such $\overline{a_1a_2\cdots a_n}$ is also $g(n)$. Thus, $f(n) = 2g(n)$.
Now we want to find $g(n)$. Denote $m_k(i)$ as the $k$-digit "A wave number" whose last digit is $i$ ($i = 1, 2, 3, 4$), then
$$g(n) = \sum_{i=1}^{4} m_{n}(i).$$
As $a_{2k-1} < a_{2k}$, $a_{2k} > a_{2k+1}$, we have the following 2 cases.
(a) When $k$ is even, $m_{k+1}(4) = 0$, $m_{k+1}(3) = m_k(4)$, $m_{k+1}(2) = m_k(4) + m_k(3)$, $m_{k+1}(1) = m_k(4) + m_k(3) + m_k(2)$.
(b) When $k$ is odd, $m_{k+1}(1) = 0$, $m_{k+1}(2) = m_k(1)$, $m_{k+1}(3) = m_k(1) + m_k(2)$, $m_{k+1}(4) = m_k(1) + m_k(2) + m_k(3)$.
It is obvious that $m_2(1) = 0$, $m_2(2) = 1$, $m_2(3) = 2$, $m_2(4) = 3$, then, $g(2) = 6$.
Hence,
$$m_3(1) = m_2(2) + m_2(3) + m_2(4) = 6,$$
$$m_3(2) = m_2(3) + m_2(4) = 5,$$
$$m_3(3) = m_2(4) = 3, \quad m_3(4) = 0.$$
Therefore
$$g(3) = \sum_{i=1}^{4} m_{3}(i) = 14.$$
On the other hand, since
$$m_{4}(1) = 0, \quad m_{4}(2) = m_{3}(1) = 6,$$
$$m_{4}(3) = m_{3}(1) + m_{3}(2) = 11,$$
$$m_{4}(4) = m_{3}(1) + m_{3}(2) + m_{3}(3) = 14,$$
we obtain,
$$g(4) = \sum_{i=1}^{4} m_{4}(i) = 31.$$
In the same way, we could get $g(5) = 70$, $g(6) = 157$, $g(7) = 353$, $g(8) = 793$.
Then, in general, when $n \ge 5$,
$$g(n) = 2g(n-1) + g(n-2) - g(n-3). \quad \textcircled{3}$$
Now we prove ③ as follows.
Using mathematical induction, we are done when $n=5, 6, 7, 8$. Suppose ③ holds when for 5, 6, 7, 8..., $n$ now consider the case for $n+1$. When $n$ is even, from (a), (b), we have
$$m_{n+1}(4) = 0, \quad m_{n+1}(3) = m_{n}(4),$$
$$m_{n+1}(2) = m_{n}(4) + m_{n}(3),$$
$$m_{n+1}(1) = m_{n}(4) + m_{n}(3) + m_{n}(2).$$
As $m_n(1) = 0$, then
$$\begin{align*} g(n+1) &= \sum_{i=1}^{4} m_{n+1}(i) \\ &= 2\left(\sum_{i=1}^{4} m_{n}(i)\right) + m_{n}(4) - m_{n}(2) \end{align*}$$
$$= 2g(n) + m_n(4) - m_n(2).$$
Since
$$\begin{aligned} m_n(4) &= m_{n-1}(1) + m_{n-1}(2) + m_{n-1}(3) + 0 \\ &= \sum_{i=1}^{4} m_{n-1}(i) = g(n-1), \end{aligned}$$
$$\begin{aligned} m_n(2) &= m_{n-1}(1) = m_{n-2}(4) + m_{n-2}(3) + m_{n-2}(2) + 0 \\ &= g(n-2). \end{aligned}$$
We obtain,
$$g(n + 1) = 2g(n) + g(n - 1) - g(n - 2).$$
On the other hand, when $n$ is odd, $g(n+1) = \sum_{i=1}^{4} m_{n+1}(i)$.
$$\text{Since } m_{n+1}(1) = 0, \quad m_{n+1}(2) = m_n(1), \quad m_n(4) = 0,$$
$$\begin{aligned} m_{n+1}(3) &= m_n(1) + m_n(2), \\ m_{n+1}(4) &= m_n(1) + m_n(2) + m_n(3), \end{aligned}$$
then,
$$\begin{aligned} g(n + 1) &= \sum_{i=1}^{4} m_{n+1}(i) \\ &= 2 \sum_{i=1}^{4} m_{n}(i) + m_{n}(1) - m_{n}(3) \\ &= 2g(n) + m_{n}(1) - m_{n}(3). \end{aligned}$$
Since
$$m_n(1) = m_{n-1}(4) + m_{n-1}(3) + m_{n-1}(2) + 0 = g(n-1),$$
$$\begin{aligned} m_n(3) &= m_{n-1}(4) = m_{n-2}(1) + m_{n-2}(2) + m_{n-2}(3) + 0 \\ &= g(n-2). \end{aligned}$$
We get
$$g(n + 1) = 2g(n) + g(n - 1) - g(n - 2).$$
Hence, ③ holds for $n+1$. By mathematical induction, ③ holds when $n \ge 5$.
From ③,
$$g(9) = 2g(8) + g(7) - g(6) = 1782,$$
$$g(10) = 2g(9) + g(8) - g(7) = 4004.$$
Thus,
$$f(10) = 2g(10) = 8008.$$

(2) Now consider the sequence of remainders of $\{g(n)\}$ divided by 13. From ③, when $n = 2, 3, 4, \dots, 14, 15, 16, 17, \dots$, the corresponding remainders are 6, 1, 5, 5, 1, 2, 0, 1, 0, 1, 1, 3; 6, 1, 5, 5, ...
Therefore, when $n \ge 2$, the sequence of remainders is a periodic sequence whose minimum period is 12. As
$$2008 = 12 \times 167 + 4,$$
we get
$$g(2008) \equiv 5 \pmod{13}.$$
Therefore,
$$f(2008) \equiv 10 \pmod{13}.$$