I would suggest that you go for MS in Stats. A good foundation of machine learning comprises of mathematics, statistics and computer science. A graduate degree in statistics should equip you in the first two fields by providing a systematic and in-depth education in those fields. As far as computer science is concerned, most of its education takes place online anyway so you can learn (or rather pick up) anything you want from the internet itself.
Further, in terms of employability - there's far more software engineers than applied statisticians who can code. If you're serious about working in machine learning, as a statistician with a theoretical and practical understanding of ML, you'll be far more in demand and far less replaceable. (Not that software engineers have poor employment prospects, but assuming we're talking exclusively ML heavy roles here).
Remember that the market has two sides, however. There are many software engineers because companies need more software engineers. Also note that a CS program gives you flexibility in learning to code and specializing in ML/statistics.
I'm surprised to see strong support for the MS in Stats. I'll make the argument for a MS in CS (which I'm finishing now).
First, and most importantly: any decent CS program will let you take electives. I'd suggest taking ML and statistics classes for yours; to that end, make sure your school has a decent statistics department!
I can say, with certainty, that smaller teams will not hire a stats/ML specialist. Small teams search for broad skill sets to maximize for productivity. If you haven't studied CS, you can use a MS in CS to develop the broad engineering/analytical skill set smaller teams desire.
Regarding "picking up computer science online," be careful not to confuse software engineering with computer science. As a data scientist, you need to understand how algorithms and advanced data structures (read: not just stacks and queues!) perform. You might need to think about whether your current problem is NP-hard. You will also need to reason about convergence rates. CS theory covers all of these topics.
Finally, studying scientific computing as part of a good CS program will prepare you for all sorts of real-world issues: writing well-factored code, performance issues, numerical precision issues, etc. You can definitely pick this up in a math program, though...
At NYU, "a few" is actually 8 of 12 required classes. This granted me enough flexibility to take the math classes (scientific computing, linear algebra, optimization, stochastic calculus) and ML classes (learning theory, graphical models, survey class with emphasis on deep learning, independent study) I felt would best prepare me for this type of work.
The core classes -- languages, algorithms, OS, a capstone -- are also relevant if you plan to code.
Also note that "statistical theory" comes at a price: 2 years of statistical theory means 0 years of formal CS or engineering training.
I would suggest be a statistician who knows a decent amount of computer science (in other words, someone who knows the serious limitations of R, can program in other languages, and use them to their full capabilities).
As always, it depends, most crucially on your background (bachelors degree), and how you performed in it....
As someone who has done his masters in CS after a bachelors degree in the field, I'd say definitely go for statistics.
Grasping the theoretical foundations would probably be better there. It would be easier to catchup on the CS 'technicalities' you'd be missing, rather then those.