I recently heard a tape that went through the procedure for changing ones name. It is similar to the procedure for adding a name, but not quite. The magid shiur on the tape said that there is a specific set of brachos that must be said during an aliyah to the torah for it to be valid. He said that it can be found in some sefardi siddurim.
The main method involves being called to the Torah with the new name and certain brachos recited establishing the new name as belonging to the new person that one has become. Rav Moshe Feinstein says that once the new name is used in front of a minyon, and the person called to the torah by that name, the name has changed. The person then uses the new name for all purposes and is treated like Avraham or Yaakov.
See The Halacha of Changing One’s Jewish Name Summary provided by Rabbi Levi Alter
In Shulchan Aruch Even Haezer 129 Bet Shmuel 33, Igrot Moshe by Rabbi
Moshe Feinstein, Even HaEzer IV 104, states: “A name that a person is
called by for thirty days becomes one’s Halachic name.” We change the
name by the recitation of Tehillim in the presence of a Minyan with
special Tefillos, including a Yehi Ratzon, for a name which symbolizes
life (Chaim, Chaya), health (Raphael, Raphaella), strength (Gabriel,
Gabrielle), or hope (Tikva).