その手続き型でのカウンタ変数を蓄積引数にするだけ

solve = solve' 0
　where
　　solve' 2 _ = True
　　solve' _ [] = False
　　solve' n (x:xs) = solve' (if even x then (n+1) else n) xs

main = print $ solve [1,3..1000001]