@Mayou's answer and @Halil's comment point out typical situations in which you observe such behaviour.
Let me add that you observe model instability - this should give you a search term to start looking up what can be done.
How can I rely on my results seeing this behavior?
These validation results tell you that you cannot rely on the predictions of your model: the models are so unstable that predictions for the same test case (each case is tested once during each run) are all over the place.
This may be a valid result in case you're doing an exploratory analysis, but if your task is to set up a classifier for prediction, you need to go back to classifier modeling. See below.
Does this mean that the number of folds is too less or too much?
No. Typically the problem is not the cross validation setup but the modeling.
(You may have unstable surrogate models for the cross validation but a reasonably stable model of the whole data set if the surrogate models are trained on a small fraction of all cases. In practice, I've never seen that repeated/iterated cross validation indicates huge instability in situations where the whole data model isn't unstable as well: noone does 2-fold CV in situations where low but reasonable numbers of cases are available.)
What should I do?
Go a bit deeper into measuring model stability with repeated/iterated cross validation. The overall indicator is no very sensitive detector for model instability. Here's one of our papers discussing how to measure stability of the prediction with repeated/iterated cross validation: Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6
Read up on model stability.
You can improve model stability by e.g.:
- not doing data driven model optimization (i.e. decide hyperparameters without the use of an inner cross validation loop)
- use stronger regularization
- use model aggregation,
e.g. random forest instead of a decision tree. You can also aggregate the cross validation surrogate models as we did in the paper linked above.
- consider using a classification algorithm that is more stable (stronger regularization, fewer hyperparameters/hyperparameters that can more easily be set by expert knowledge or experience or other non-data-dependent indicators)
- more samples will always beat all kinds of fancy heuristics