How to do k-fold validation with classifiers?
So I cannot calculate the MSE of validation folds, there is no MSE
  here.


The question that you firstly need to ask is "how do I evaluate my model".

Since the model is a classifier, you can use the accuracy (number of correct classifications over the overall attempts) or the F-score as measures of your model's performance. Based on the chosen measure, you will thereafter evaluate the results of kfold-validation.