We introduce an algorithm that is simultaneously memory-efficient and low-scaling for applying ab initio molecular Hamiltonians to matrix-product states (MPS) via the tensor-hypercontraction (THC) format. These gains carry over to Krylov subspace methods, which can find low-lying eigenstates and simulate quantum time evolution while avoiding local minima and maintaining high accuracy. In our approach, the molecular Hamiltonian is represented as a sum of products of four MPOs, each with a bond dimension of only 2. Iteratively applying the MPOs to the current quantum state in MPS form, summing and recompressing the MPS leads to a scheme with the same asymptotic memory cost as the bare MPS and reduces the computational cost scaling compared to the Krylov method using a conventional MPO construction. We provide a detailed theoretical derivation of these statements and conduct supporting numerical experiments to demonstrate the advantage. Our algorithm is highly parallelizable and thus lends itself to large-scale HPC simulations.