I've always liked the interpretation Quillen gave in his "On the group completion of a simplicial monoid" paper (Appendix Q in Friedlander-Mazur's "Filtrations on the homology of algebraic varieties"). Here is a somewhat revisionist version.
Associated to a monoidal category C, you can take its nerve NC, and the monoidal structure gives rise to a coherent multiplication (an A∞-space structure) on NC. (If you work a little harder you can actually convert it into a topological monoid.)
May showed in his paper "The geometry of iterated loop spaces" that an A∞-space structure on X is exactly the structure you need to produce a classifying space BX, and there is a natural map from X to the loop space Omega(BX) that is a map of A∞-spaces, and is a weak equivalence if and only if π0(X) was a group rather than a monoid using the A∞-monoid structure. In fact, Omega(BX) satisfies this property, and so you can think of it as a "homotopy theoretic" group completion of the coherent monoid X.
What Quillen showed was that you can recognize the homotopy theoretic group completion in the following way: the homotopy group completion of X has homology which is the localization of the homology ring of X by inverting the images of π0(X) in H0(X). Moreover, the connected component of the identity in the homotopy group completion is a connected H-space, so its fundamental group is abelian and acts trivially on the higher homotopy groups.
In particular, if X is the nerve of the category of finitely generated free modules over a ring R, then X is homotopy equivalent to a disjoint union of the classifying spaces BGLn(R), with monoidal structure induced by block sum. The monoid π0(R) is the natural numbers N, and so you can consider the map
X = coprod_(n∈N) BGL_n(R) → coprod_(n∈Z) BGL(R)
to a union of copies of the infinite classifying space. This map induces the localization of H*(X), so the space on the right has to have the same homology as the homotopy group completion, but the problem is that the connected component of the identity on the right (BGL(R)) doesn't have an abelian fundamental group that acts trivially on the higher homotopy groups, so this can't be the homotopy group completion yet.
So this leads to the plus-construction: to find the homotopy group completion you're supposed to take BGL(R) and produce a new space, which has to have the same homology as BGL(R), and which has an abelian fundamental group (plus stuff on higher homotopy groups). This is what the plus-construction does for you.
Quillen's Q-construction contains within it the symmetric monoidal nerve construction (you can consider just the special exact sequences that involve direct sum inclusions and projections), but it's got the added structure that it "breaks" exact sequences for you. I wish I could tell you how Quillen came up with this, but this is the best I can do.
I am neither a K-theorist nor a historian, so I don't know all the things the led to Quillen to his definition(s) of higher K-theory, but I thought I'd mention one striking application that can be found in his original paper. The Chow group of a variety $CH^p(X)$ is the group of codimension $p$-cycles modulo rational equivalence. For lots of reasons, it was desirable to express this in terms of sheaf cohomology. For $p=1$, $CH^1(X)=Pic(X)= H^1(X, O_X^*)$ was known for a long time. This can be recast into K-theoretic terms, by observing, using Bass' definition, that $O_X^*$ can be identified the sheaf associated to $U\mapsto K_1(O(U))$. I believe Bloch extended this to $CH^2$ using Milnor's $K_2$. And finally Quillen proved that $CH^p(X)=H^p(X,K_p(O_X))$ for any regular variety, and any $p$ using his definition.
Best Answer
Firstly, there is a proof using the motivic spectral sequence (the Atiyah-Hirzerbruch style spectral sequence from motivic cohomology to algebraic $K$-theory). This is written in the master's thesis of Gabe Angelini-Knoll.
Gabe and Andrew Salch are also working to answer this question and a paper is apparently due. From Andrew's website:
"My student Gabe Angelini-Knoll and I have been working on the problem of computing the Waldhausen algebraic K-groups of the algebraic K-theory spectra of certain finite fields. This is an example of "iterated K-theory" and Rognes' redshift conjecture is not known in these cases. Thus far, Gabe and I have (with the aid of a new "THH-May" spectral sequence for computing topological Hochschild homology) computed the homotopy groups of THH(K(F_q)) smashed with the p-primary Smith-Toda complex V(1), for p > 3 and for many (but not all) prime powers q. Gabe is working on the computations of the homotopy groups of the C_p fixed points of this spectrum (this will probably be Gabe's thesis), with the goal of using trace methods to recover the K-groups of K(F_q).
We expect to post and submit our first two papers on this topic before the end of summer 2016. "