Counting length-k increasing subsequences in a permutation
According to Kim, finding one such sequence is equivalent to finding a maximum independent set in a permutation graph and can be done in $O(n\log n)$ time. The running time you're looking for suggests you already knew about that, but if not, looking at citing papers might help.

Update: actually, the complement of a permutation graph is also a permutation graph, and the complement of an independent set is a clique, so unless I'm missing something, maximising the number of increasing sequences of length $k$ in your permutation should be equivalent to partitioning a permutation graph into as many $K_k$'s as possible. Surely this has been studied, at least for triangles...