Since $(a_n)$ is bounded, $S$ is nonempty and bounded above. So by AoC there exists an upper bound $s=\sup S$.
Consider $s-\frac1k$ and $s+\frac1k$ where k is an arbitrary but fixed natural number. Since any number smaller than $s$ is not an upper bound of $S$, so $\exists (s'\in S)(s-\frac1k < s')$. Observe the property which forms $S$, by transtivity of $<$, $s-\frac1k$ also has the property: $s-\frac1k < a_n$ for infinitely many terms $a_n$. Apply this similar reasoning on $s+\frac1k$ we can see that $s+\frac1k \notin S$, so there are none or only finitely many terms $a_n$ satisfying $1+\frac1k < a_n$, this is the same as saying there are infinite many terms $a_n$ satisfying $a_n \ge 1+\frac1k$. Combine these two parts we get: for all $k\in N$, there are infinitely many terms of $a_n$ satisfying $s-\frac1k < a_n \le s+\frac1k$.
The last statement gave us a hint of how to build a subsequence of $(a_n)$. For every different $k\in N$, we can pick a term from infinitely many terms that satisfy that inequality. For example we can pick $a_{n_1}$ from $\{a_n : s-1<a_n<s+1\}$. After we picked $a_{n_k}$, we only need to satisfy $n_{k+1}>n_k$ to make this is indeed a subsequence, no repeatition or backward happened. (This is always can be done because for every pick we have infinitely many terms in hand)
Then we need to check whether this subsequence $(a_{n_k})$ converges to something. By intuition this should be $\sup S$. To satisfy the inequality $|a_{n_k}-s|<\epsilon$ for every $\epsilon >0$, choose $K>\frac1\epsilon$. If $k\ge K$ then $\frac1k < \epsilon$ which implies $$s-\epsilon < s-\frac1k < a_{n_k} \le s+\frac1k < s+\epsilon$$
So the B-W theorem has been proved using AoC.
The proof doesn't assume that one of the half-intervals has infinitely many terms while the other has finitely many terms; it only says that at least one of the halves has infinitely many terms, and one can be chosen arbitrarily. In fact, if $[a_n,\frac{a_n+b_n}{2}]$ and $[\frac{a_n+b_n}{2},b_n]$ both have infinitely many terms, the process used in the proof may be applied to both intervals, and thus there are at least two subsequences converging to different values. This is the case for your example of $(-1)^n$, since there are subsequences converging to both $1$ and $-1$.
Best Answer
To expand on what @DonAntonio said:
Assume there are only a finite number of sequence elements in one half of the interval. Then there must be an infinite number in the other half.
So in the context of the proof, you pick one half (doesn't matter which one). If it already has an infinite number of the sequence elements, move on to the next step. Otherwise, the other half has an infinite number of the sequence elements, so take that one instead. All we wanted to do is prove that at least one of the halves contains an infinite sub-sequence ... done.
Doing this step repeatedly lets you get infinite sub-sequences within smaller and smaller intervals. If, for example, we then choose an element from each of the intervals we obtain in this manner, we can derive an infinite sub-sequence that converges.
The statement you were taking in your question is actually not true (that one of them has to contain a finite number of sequence elements). Consider the bounded sequence: $$a_n=(-1)^n$$
When we perform our halving process the first time (starting with $[-1,1]$), both of the resulting intervals have an infinite number of sequence elements.