Nació el 22 de octubre de 1939^[2]​ en Fernando de la Mora, Paraguay. Es hijo de Pedro Regalado Medina (†) y María Antonia Salinas (†).^[5]​

Realizó sus estudios de humanidades y filosofía en el Seminario San José de San Juan Bautista, y cursó teología en la Pontificia Universidad Gregoriana.^[5]​

Fue ordenado sacerdote el 17 de mayo de 1970 por el papa Pablo VI en la Basílica de San Pedro.^[5]​ A su regreso a Paraguay, asumió la parroquia Nuestra Señora de la Asunción en San Juan Bautista. Tras el fallecimiento de monseñor Ramón Bogarín Argaña, fue nombrado vicario capitular de la Diócesis de Misiones y Ñeembucú. El 10 de agosto de 1980, fue consagrado obispo de la Diócesis de Benjamín Aceval.^[5]​

Su consagración episcopal tuvo lugar el 10 de agosto del mismo año, siendo ordenado por Joseph Mees, nuncio apostólico en Paraguay. Posteriormente, el 22 de agosto de 1999, asumió como obispo titular de la Diócesis de San Juan Bautista de las Misiones.^[5]​

Se retiró el 26 de marzo de 2017 tras cumplir setenta y cinco años de edad, en conformidad con lo establecido por el Código de Derecho Canónico,^[1]​ que indica que los obispos deben presentar su renuncia al papa al alcanzar dicha edad,^[6]​ tras lo cual fue nombrado obispo emérito.^[5]​

En la Conferencia Episcopal Paraguaya (CEP), Medina ocupó diversos cargos, incluyendo la secretaría ejecutiva de varios equipos y la responsabilidad de la Pastoral Social Nacional. Fue tesorero de la CEP y, en 2005, obispo responsable de la Coordinación Nacional de Comunidades Eclesiales de Base.^[7]​

Durante la dictadura de Alfredo Stroessner, Mario Melanio Medina se destacó como un firme defensor de los derechos humanos, lo que llevó al régimen a tildarlo de «obispo rojo».^[8]​ A pesar de las calumnias en su contra, sostuvo una postura inquebrantable en favor de la democratización del país.^[7]​

Tras la caída de la dictadura, continuó su labor en defensa de los sectores más vulnerables, consolidándose como una figura reconocida dentro de la Iglesia católica paraguaya.^[7]​

Ha abogado por los derechos de campesinos e indígenas, así como por la implementación de políticas ambientales sostenibles.^[9]​ Ha denunciado la corrupción,^[10]​^[11]​ el nepotismo^[10]​ y la debilidad del sistema judicial, promoviendo la transparencia, el acceso a la salud y la movilización ciudadana como pilares de la justicia social y la democracia en Paraguay.^[12]​

Medina ha criticado las estructuras políticas tradicionales y la corrupción en las instituciones, denunciando la fragilidad del sistema judicial y la falta de transparencia en la gestión pública. Aboga por una democracia más participativa y un sistema de justicia más sólido y accesible para todos los ciudadanos.^[13]​

Aunque explícitamente no se ha alineado con un partido político, Mario Melanio Medina ha mostrado simpatía por la oposición, especialmente por Efraín Alegre, a quien considera un político íntegro.^[13]​ Según sus declaraciones, una oposición unida, enfocada en la justicia social y las necesidades del pueblo, es clave para abordar los principales problemas del país, como la pobreza, la inseguridad y la desigualdad social.^[13]​