Let me walk you through the evaluation of your function. Note that you can use Trace to see how your function evaluates. I particularly like Trace with the Option TraceOriginal-> True.
Anyway in Mathematica there is something called the "Main Loop", determining how expressions get evaluated. It is good to realize that in "simple cases" (non simple cases would include cases in which functions have Attributes or functions like Evaluate or Unevaluated are present) the arguments of any function will be evaluated before rules associated with the function itself will be used.
Suppose for convenience that A is not set. And suppose for convenience that you used the underscores as I suggested in my comment.
pol4[A,10] will evaluate as follows
first Mathematica will evaluate A and 10. As it is, evaluating them will just yield A and 10 again respectively. When Mathematica has evaluated all the arguments, it will find rules associated with "the head" (function that surrounds the expression being evaluated) pol4. It finds your rule pol4[A_, 1] := A (or maybe you can think of it like HoldPattern[pol4[A_,1]]:> A (which is really a rule that was generated by your definition that can be retrieved by doing DownValues[pol4])). This rule does not match however, so Mathematica moves on to the next rule, which is the rule associated with pol4[A_, n_Integer?Positive] := A.pol4[A, n - 1]. So far so good.
We get, after applying this rule
A.pol4[A, 9]
This expression has as its fullForm
A.pol4[A, 9] // FullForm
-> Dot[A,pol4[A, 9]]
Mathematica looks at the first argument of Dot, A, but there is nothing to do. Then it looks as the second argument (before evaluating Dot). This is where you might start to feel worried. We are going to evaluate pol4[A,9] before evaluating Dot. pol4[A,9] will evaluate similarly to pol4[A,10] and there will be another Dot function that will be evaluated only after all the pol4's are evaluated. If more than 255 Dots are generated this way, your recursionlimit is reached.
I like to think of the stack as just a tree of expressions. We would have after two iterations
Dot[A, evaluating ----> Dot[A, pol4[A, 8]]]
and after three iterations
Dot[A, Dot[A, evaluating ----> Dot[A, pol4[A, 7]]]]
Do you see all how a lot of Dot's get put on the Stack?
Solution
I'm not exactly sure what kind of solution you are after. If you just want to take the power of a matrix, you can do
MatrixPower[A, 1000]
If you want to apply some function iteratively, you can do
With[{A = A},
Nest[A.# &, A, 1000]
]
The "what Jacob calls the Mr.Wizard style of doing things" would be
ggg[n_, total_] := ggg[n + 1, A.total];
ggg[1000, total_] := total
ggg[1, A]
Which is a nice example of an "tail recursion" that does not reach $RecursionLimit. If you want to have tools for automatically getting tail recursions, you might want to use (not study, it is very advanced) Leonids Answer here. Below that is the answer what the "Mr.Wizard style of doing things" refers to.
I suppose Mr.Wizard would argue that something like the above can always be written as
Fold[A.# &, A, Range[1000 - 1]]
Which he would never use as there is the possibility to use Nest and of course MatrixPower in this case... But still :). The last two approaches can be ideas for cases in which you want to "do something with your counter".
