[OED:] Etymology: For forth with (preposition), = earlier forth mid, along with, see forth adv. 2c. The adverb forthwith originates from this phrase, the preposition being used absol. or with ellipsis of its regimen.
[forth adv. 2c] †c. In early Middle English forth mid, later forth with = ‘along with’. Also absol., along with him, them, etc.: at the same time with something else.
at the same time … does not mean 'immediately'. Per this answer, with can mean 'with' or 'against'; so I don't know how to disambiguate it.
Here's my guess at the etymology: Suppose you want to proceed forth with X. Then X may need be completed immediately.
Please allow me to verify, to avoid deluding myself with false etymologies.
Best Answer
This very query has just been answered by World Wide Words. Here's an extract: