Thank you for the patches and for addressing my comments.
Your work is really appreciated.

Overall it looks in a good shape now.
Please fold all the patches into one, so it's better maintainable.
I have only the following remaining comments:

+++ configure.ac
1) Please use autoconf macros AC_CHECK_TYPE/AC_CHECK_TYPES for checking Elf{32,64}_Chdr typedefs.
See for example:
https://www.gnu.org/software/autoconf/manual/autoconf-2.69/html_node/Generic-Types.html#Generic-Types

+++ coregrind/m_debuginfo/image.c
2) When including "tinfl.c", do we want to define "TINFL_HEADER_FILE_ONLY"?

3) typo:
+   // Virtual size of the image = real size + size of uncopressed data
uncopressed => uncompressed

4) typo:
+   // Number of compressed slices are used
delete 'are'

5) CEnt.data has now non-fixed size. Why CACHE_ENTRY_SIZE is still used in various places
around image.c; for example in alloc_CEnt() and realloc_CEnt()?

6) In function find_cslc(), please use {} braces for better readability and put 'return' statement
to its own line. You can declare 'i' inside the for loop as we use C99.

7) In function find_cslc(), use proper type 'UInt' instead of 'int', to match that of 'cslc_used'.

8) Width of all lines is 80 characters max - occurrences in alloc_CEnt(), realloc_CEnt(), get_slowcase(), ML_(img_mark_compressed_part)().

9) Should be two lines, really:
+   if (len > ce->size) len = ce->size;

10) typo:
+         // get copressed data

11) should be on separate lines:
+         if ((cslc != NULL) && (cslc->szD > CACHE_ENTRY_SIZE)) size = cslc->szD;

12) Please be explicit:
+   vg_assert(img);
=> vg_assert(img != NULL);

+++ coregrind/m_debuginfo/priv_image.h
13) Make it a proper sentence:
+/* Real size of the image */
=> +/* Real size of the image. */

14) Make it a proper sentence:
+   Returns (virtual) position in image from which decompressed data can be read */
=>  Returns (virtual) position in image from which decompressed data can be read. */

15) Lines too long (exceed 80 chars):
   Returns (virtual) position in image from which decompressed data can be read */
DiOffT ML_(img_mark_compressed_part)(DiImage* img, DiOffT offset, SizeT szC, SizeT szD);


+++ coregrind/m_debuginfo/readelf.c 
16) Magic '12' is used multiple times, please make it a #define or a constant.
+    } else if (h->sh_size > 12) {

17) [multiple times] The exclamation mark is really unnecessary here,
the whole message you get is scary per se (check other occurrences of ML_(symerr)() in this module).
+                     ML_(symerr)(di, True, "   Unknown compression type!"); \

+++ memcheck/tests/Makefile.am
18) Use @FLAG_W_NO_UNINITIALIZED@ (see configure.ac) instead of plain -Wno-uninitialized.

+++ memcheck/tests/cdebug.c
19) A compiler could see that the program always returns 0 and might optimize 'if (x)' out.
Perhaps you can return different values?

20) I don't see any coregrind/Makefile changes to build m_debuginfo/tinfl.c?

+++ coregrind/m_debuginfo/tinfl.c
21) What kind of license your modifications fall under? tinfl.c seems to be under "UNLICENSE" whereas
the rest of Valgrind is under GPLv2+.

22) We should use proper Valgrind types, not standard C ones here:
typedef unsigned char mz_uint8;
typedef signed short mz_int16;
typedef unsigned short mz_uint16;
typedef unsigned int mz_uint32;
typedef unsigned int mz_uint;
typedef unsigned long long mz_uint64;


I was able to get it built on amd64/Solaris and regression testing went fine.
However I don't have any system with toolchain supporting '-gz' at hand.
I assume you tested on MIPS. Anyone can test on a different architecture or distribution?