Solving a T(n) recursion without Master Theorem
Start with
$$T(1)= 1$$
$$T(21)= T(1)+\log(21)$$
$$T(41)= T(21)+\log(41)$$
$$\dots$$
$$T(20k+1)= T(19k+1)+\log(20k+1)$$
Then move $T(i)$s from the right side to the left side
$$T(1)= 1$$
$$T(21) - T(1) = \log(21)$$
$$T(41) - T(21) = \log(41)$$
$$\dots$$
$$T(19k+1) - T(18k+1) = \log(19k+1)$$
$$T(20k+1) - T(19k+1) = \log(20k+1)$$
And sum the left and right sides

$$T(20k+1) = 1 + \log(21) + \dots + \log(20k+1) \leq 1 + \sum_{i=1}^{k}{\log(21i)} = $$ 
$$1 + \sum_{i=1}^{k}{[\log(21)+\log(i)]} \leq 1+ \sum_{i=1}^{k}{\log(21)}+ \sum_{i=1}^{k}{\log(k)} = $$ 
$$1 + k\log(21) + k\log(k)$$ which is $O(n\log{n})$. This was only upper bound.

More general case

There is nothing special with the integers 1 and 20. You could take any positive integers instead of 1 and 20 and solve the relation

$$T(b) = c$$
$$T(n)= T(n-s) + \log{n}$$
as
$$T(b) = c$$
$$T(s+b) = T(b) + \log{(s+b)}$$
$$T(2s+b) = T(s+b) + \log{(2s+b)}$$
$$\dots$$
$$T((n-1)s+b) = T((n-2)s+b) + \log{((n-1)s+b)}$$
$$T(ns+b) = T((n-1)s+b) + \log{(ns+b)}$$
which gives 
$$T(ns+b) = c + \log{(s+b)}+\log{(2s+b)}+\dots + \log{(ns+b)}$$

Is $n\log{n}$ a lower bound for this relation?

UPDATE: Omar's post attempts to establish a lower bound.