k-fold cross validation with RNNs
TL;DR
Use Stacked Cross-Validation instead of traditional K-Fold Cross-Validation.
Stacked Cross-Validation
In Sckit-learn, this is called TimeSeriesSplit (docs).
The ideas that instead of randomly shuffling all your data points and losing their order, like you suggested, you split them in order (or in batches).
Belows is a picture of traditional K-Fold vs Stacked K-Fold. They both have K=4 (four iterations). But in the traditional K-Fold all the data is used all the time, whereas in the Stacked K-Fold only the past data is used for training and the now data for testing.


Strategy

Split your data in a Stacked K-Fold fashion.
At every iteration, store your model and measure its performance against the test set.
After all iterations are over, pick the stored model with the highest performance (might not even be the last one).

Note: This is a common approach in training neural nets (batching with validation sets).