How do I submit interdependent papers? I recently submitted a paper for publication and received feedback that the paper was too complex. It contained two relatively independent concepts. The material would best be served by splitting it into two papers and submitting them independently.

I have to say I agree with this editorial analysis.

However, I am now stuck as to what to do. The first concept can stand on its own, but it is largely useless without the second one. The second one has to assume the first one exists so it can build upon it.

But, as I understand it, for a journal (or a good one, anyway) to publish an article, its research must be not only sound but properly justified as well. Only, I can't justify the research in the first article without referring to the second one, and I can't present the research in the second one without using the first one as a basis.

To further complicate the matters, I'm working at an intersection, and the two articles would probably work best if submitted to different journals in somewhat different fields.

How do I format my abstracts, introductions and conclusions to pass this message across and improve my chances of acceptance?
This is one of the things pre-print services can address quite readily, even for fields that don't normally use preprints. Putting both papers on arXiv (or another field-equivelent) allows them to exist in a citable form, and as one or both of them make it through the publication cycle, the linking citation can be updated to reflect this. FigShare will also let you upload documents and provide you with a DOI, though I've never actually seen this done in practice, and it's likely arXiv or an equivalent is more appropriate for a full-sized manuscript.

If you're in a field that has conference presentations and the like that aren't equivalent to publication (for example, much of biomedicine) you may also be able to cite a poster or presentation given at a conference.