How would one say "methinks" in German? An example being, "Methinks he has changed the locks!" or "She is unwell, methinks"
Google translate suggests "michdünkt". Would "es scheint mir" be better?
The two translations you listed are to be seen as synonymous. Although "mich dünkt" is hardly used in "modern" German, as opposed to German in the era of classic poetry where the term "es scheint mir" had not even been coined.
In Shakespeare's play Hamlet, Queen Gertrude speaks the following line when Hamlet asks her, "Madam, how like you this play?"
Nowadays this line is usually misquoted as "Methinks the lady doth protest too much."
"Methinks" today is as obsolete as "doth" (we write "does" now). The only exception is when people want to inject a note of snark. They may quote the modern version of Shakespeare's line in toto when they want to signal incredulity, or they will preface a sarcastic remark with "methinks"; sometimes, the writer wants to convey the idea of a timid person speaking up hesitantly. That, however, is as regards English usage.
The translations chosen by the most influential German translators of Hamlet -- Christoph Martin Wieland (published 1766) and August Wilhelm Schlegel (published 1798) -- use language that is considered as antiquated in contemporary German as "methinks" is in modern English:
You can still write sentences in contemporary German with "mich deucht" or "mich dünkt" but only if you are aiming for effect. What kind of effect depends on context and audience; "mich deucht/dünkt" is less of a standard rhetorical device than "methinks" is in English. Leave this to experienced writers who know exactly what they are doing and why.
"Es scheint mir" is simply a German equivalent for "It seems to me".