Is it considered stealing if I use a Mikvah without paying, and if yes, is the Tevilah useless?
It is absolutely forbidden.
See also:
Halacha2go.com article #487: Can I let someone who forgot his card go through the turnstile with me?
Though the immersion is still valid after the fact, it is absolutely ridiculous to immerse in order to receive purity and holiness while at the same time violating such a severe sin which even teshuvah and yom kippur do not atone for until such time that one returns the theft.
Sources:
באמת יש לדון מדין מהבב״ע, ונפק״מ גם – ועיקר – לטובל כלים בגניבה אי חייב לחזור ולהטבילם.
אבל כמה תשובות בדבר – שקרקע אינה נגזלת, אא״כ נאמר שדין המים כתלוש ומקפיד על מימיו (ולהעיר מאבנ״ז יו״ד רעא שהעיקר במקוה הקרקע). ועוד שאין המצוה בהטבילה – גם בטבילת כלים ונדה – כ״א בהתוצאה. ובכגון דא ל״ש מהבב״ע. ועדיפא טבי״ע שלא משום טומאה נגעו בה אלא כדי שלא מצויין אצל נשותיהן כתרנגולים. ובסגנון אחר, שטבילה היא מתיר או הכשר מצוה ולא מצוה. ובמצוה שאינה חיובית, גם ל״ש מהבב״ע. ובטבילת עזרא אי״ז מצוה כלל ובמכ״ש ממצוה דרבנן שלכמה דעות ל״ש מהבב״ע. ובפרט, אם נאמר שהאיסור והגניבה בהכניסה לבנין מקוה ללא תשלום, שאין כאן עבירה במעשה המצוה. וכלתה העבירה קודם מעשה המצוה. וראה בכעי״ז בנודר מהמעיין וטבל בימות החמה – תהל״ד לקוטים בסוף או״ח ח״א. מהרש״ג ג, יט (ושם גם בטבל ביו״כ).
אלא שסו״ס המצוה באה לידו ע״י עבירה. ולא לרצון יהי׳. ולפעמים ה״ז גם גזל הרבים רח״ל. ובטבילה משום תשובה חמור טפי. ושו״ר שדן מזה בטהרת התורה ב, ז, כח במקור הטהרה מו. ושם ר״ל משום אעל״מ.
וילה״ע מס״ח תשעב בהתפלל בסידור גזול שהתפלה לא עלתה לו. ובברית עולם להחיד״א הקשה שה״ז כקורע בשבת שבירושלמי שבת יג, ג, דאיהו עבר עבירה אבל המצוה אינה בעבירה. ודומה יותר למעביר מצה מרה״י לרה״ר, שבירושלמי שם. ואולי כוונת ס״ח שאין התפלה לרצון, ותו לא. ועוד כתבו שתפלה חמור יותר שהוא בגדר בוצע ברך – ראה כעי״ז שו״ת אג״מ או״ח ב, יז לענין סידורים שנדפסו בשבת, שאין קטיגור נעשה סניגור. וכ״בפה בס״ח גופא רמט, לענין ספר שכתבו רשע. ואולי גם בנדו״ז שייך כעי״ז, שכל עיקר גדר אין קטיגור נעשה סניגור שייך בדבר הבא לרצות, וכן כאן שהמקוה בא לטהר, ואא״פ להיטהר במעשה עבירה. ובירושלמי סוכה רפ״ג, מצינו שעל לולב הגזול אמרו שאין קטיגור נעשה סניגור. ואולי לפי שבא לרצות, אף שהוא בחוץ. וראה שו״ת בא״מ ו, רלה.
ואף שמקוה מטהר טמאים גם כשנשאר טמא בטומאה אחרת, וכן בכפרת עונות – ראה לקו״ש יז ע׳ 180 ואילך – אבל כאן העבירה בכניסה למקוה גופא, והיינו שהמצוה והכפרה נגרמה ע״י העבירה, וע״ד כרת דיומא, ראה צפע״נ יבום ד, ב. לקו״ש יא ע׳ 2.
#14301