Je peux avancer une hypothèse de grande admiratrice d’Albert Cohen.
Il est probable, que cet auteur inventif, d’origine grecque ait employé « mal » dans un sens négatif :
– Par exemple, il a eu mal, il s’est fait mal, il a mal travaillé…, c’est mal

Et il a utilisé aussi la négation : « ne…pas », d’où la présence de ce « ne ».

Je ne me suis pas fait mal. Je n’ai pas eu mal
Il n’a pas mal travaillé. ==>il a bien travaillé
Je ne m’en suis pas mal tiré. (phrase d’Adrien Deume)
Ce ne sera pas mal.(votre seconde phrase est-elle de Solal ?)

On peut donc avancer que le « ne…pas » a le statut d’une vraie négation et c’est l’adverbe « mal » et non la locution « pas mal » qu’il a employé.

D’ailleurs, vous écrivez vous-même que « l’expression équivaut approximativement à « beaucoup » quand elle est précédée du verbe avoir (il en a pas mal); or Albert Cohen n’emploie pas le verbe avoir …