There are two possible ways to attack this problem
Both K and K' can be expressed in terms of the Theta function as described here http://mathworld.wolfram.com/EllipticModulus.html. If you compute $\Theta_3$, you can get both at the same time.
The other way is to observe that both K and K' are expressible in terms of the hypergeometric function $_2F_1(\frac{1}{2}, \frac{1}{2} ; 1; m)$. They are solutions of the same self-adjoint Gauss hypergeometric differential equation (since the equation is invariant under the transformation (m $\rightarrow$ 1-m))
$(k^3 - k)\frac{d^2y}{dk^2} + (3k^2 -1)\frac{dy}{dk} + ky = 0 $
By virtue of this fact, both K and K' are connected. You will find the following series expansion for K'(k) derived in Borwein's book Pi and AGM Section 1.3
$ K'(k) = \frac{2}{\pi} log \frac {4}{k} K(k) - 2 [(\frac{1}{2})^2(\frac{1}{1.2}k^2 + (\frac{1.3}{2.4})^2(\frac{1}{1.2} + \frac{1}{3.4})k^4 + (\frac{1.3.5}{2.4.6})^2(\frac{1}{1.2} + \frac{1}{3.4} + \frac{1}{5.6})k^6 $.....(infinite series) + ]
You may also find Chapter 5 of Armitage and Eberlein's book on Elliptic Functions useful.
EDIT1: I put in the complete series expansion for K'(k).
Regarding the computation of E(k), E(k) and K(k) are connected by the differential equation $ \frac{dK}{dk} = \frac{E - (1-k^2)K}{k(1-k^2)} $ which is how the Legendre relation you mention above comes about.
Again Borwein has the solution for this problem(buy the book!). Exercise 3 in Sec 1.4 has the formula based on the quartic AGM iteration $ E(k) = K(k)[1 - \sum_{n=0}^{\infty} 4^n [\alpha_n^4 - (\frac{\alpha_n^2+\beta_n^2}{2})^2 ] $ where
- $\alpha_n = (a_{2n})^{\frac{1}{2}} and \beta_n = (b_{2n})^{\frac{1}{2}}$
and $ a_n, b_n$ and $c_n $ satisfy the AGM relation
