How do I filter entries by month using custom Date/Time field and paginate them? Here is how I am filtering entries by a specific month: 

{% set filterId = "July" %}
{% set allEntries = craft.entries.section('messages') %}
{% set filteredEntries = [] %}

{% for msg in allEntries %}

  {% if msg.messageDate | date('F') == filterId | date('F') %}
    {% set filteredEntries = filteredEntries | merge([msg]) %}
  {% endif %}

{% endfor %}

{% set messageList = filteredEntries %}


How can I paginate messageList? Do I need to filter by month a different way for pagination to work?
You won't be able to paginate messageList, because that's just an array... According to the official documentation on the {% paginate %} tag, only an ElementCriteriaModel can be paginated.

To see how to create an ElementCriteriaModel which has already been filtered by month, check out Solution #2 in this thread...

You'll end up with code that looks something like this:

{% set firstDayOfMonth = year ~ "-" ~ month ~ "-01" %}
{% set daysInThisMonth = firstDayOfMonth|date('t') %}
{% set lastDayOfMonth  = year ~ "-" ~ month ~ "-" ~ daysInThisMonth %}

{% set thisMonthsEntries = craft.entries.section('messages').messageDate('and', '&gt;= ' ~ firstDayOfMonth, '&lt;= ' ~ lastDayOfMonth) %}

{% paginate thisMonthsEntries as entriesOnPage %}
    {% for entry in entriesOnPage %}
        {# ... whatever your code does... #}
    {% endfor %}
{% endpaginate %}