Like those of Art Tatum, Monk's improvisations consist of playing the melody of the song and varying the accompaniment, the harmonic and rhythmic approach, the ornamentation. The melody is sometimes concealed for a stretch, but it always reemerges. On standards, like Tatum, he often comes back to a basic stride pattern to reassert the basic melody / form / harmony of the tune after a more abstract or concealed passage.

So there is little of the "blowing over the changes" improvisation in Monk (or Tatum), where the original melody is simply forgotten in favor of new, improvised melodies that relate only to the underlying harmonies. If you turn on the radio in the middle of a song and hear Monk play a standard, you will always know what song he is playing right away, even if you're bad, like me, at recognizing chord changes by themselves.

When he plays his own songs Monk still plays the melody. On Monk's Mood, Crepuscule with Nellie, Reflections, Pannonica, Ruby My Dear, do we really want a performance that effaces ;those very beautiful melodies? On more simplistic sounding Blues, his approach might be a bit different, In those cases, the recognizable blues cadence is more significant than the melody per se.

There is a bias against melody in some jazz criticism. The logic seems to be that just playing a popular song straight, without changing the melody much, unjazzlike. You find references to "These Foolish Things" as a trite melody, for example. That drives me crazy.