The HTTP specification (RFC2616 for HTTP/1.1) doesn’t define a maximum header size.
However, in practice, all servers have limits, for header numbers and header field size:
Apache 2.x: 8K
Nginx: 8K
IIS: 8K-16K (depending version)
If a request line exceed the limit a 414 Request-URI Too Large error is returned. If a request header field exceed the limit a 400 Bad Request error is returned. In order to be sure that a request will be proceed by all HTTP server, it’s better to limit the request size to not exceed 8190 Bytes (and yes that include cookie data).
If you can’t do that, the only remaining solution is to increase the limits values. For apache you can play with the LimitRequestFieldSize and LimitRequestLine parameters. For nginx take a look at the large_client_header_buffers parameter.
Keep in mind that increasing theses values to much will seriously degrade performance.