The short answer
Quote Investigator found no substantive evidence that Twain wrote or said it. The earliest close match it located is a tweet of 10 January 2011, which already gave Twain's name.
What Twain did write
The thought is not alien to him. In a passage of his autobiography dictated on 2 December 1906 and published in the North American Review, Twain wrote: “How easy it is to make people believe a lie, and how hard it is to undo that work again!” It is a related observation, but a different sentence, and it comes in a story from his own youth: years later he confessed a deception to his mother, and she would not believe the confession.
An older thought
The idea that people cling to a mistaken belief is much older. Quote Investigator points to Baltasar Gracián, in 1647, writing that the more mistaken a blockhead's judgement, the more stubbornly he holds it. The one-line version credited to Twain has not been found before 2011.